LCC/Moose '19 Contest 5 S3 - Futures

View as PDF

Points: 10 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

Tim has discovered a time machine! Tim has read enough about time travel to know that he should not do any wacky things, so he decides to be boring and serious: he will get future stock prices using the machine, then trade the stock using that information. However, he needs to be careful: if he makes more than trades in a day or has more than one active trade at a time, then he is at risk of impacting the future or being found out.

As Tim's co-founder, you're in charge of figuring out how you can maximize the profits using this knowledge (while Tim takes journeys through time). Given a series of future prices that Tim obtained which occur on the same day, can you figure out the most money that you can make using at most disjoint, single-stock trades? A trade consists of buying a stock at one point in time, then selling it at a future point in time.

Input Specification

The input begins with two integers , the number of stock prices that Tim obtained and the maximum number of trades .
The next line contains integers , the future stock prices.

For at least 30 points, .
For at least 60 points, .
For at least 80 points, .

Output Specification

Output a single integer, the maximum profit that can be made using at most disjoint stock trades.

Sample Input 1

6 2
2 3 1 3 2 5

Sample Output 1

5

Sample Input 2

3 1
3 2 1

Sample Output 2

0