LCC/Moose '19 Contest 5 S3 - Futures

View as PDF

Submit solution

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

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 K 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 N 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 K 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 N, K (1 \le N \le 10^6, 1 \le K \le 10^3), the number of stock prices that Tim obtained and the maximum number of trades K.
The next line contains N integers P_i (1 \le P_i \le 10^9), the future stock prices.

For at least 30 points, N, K \le 10^3.
For at least 60 points, N \le 10^4.
For at least 80 points, N \le 10^5.

Output Specification

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

Sample Input 1

6 2
2 3 1 3 2 5

Sample Output 1


Sample Input 2

3 1
3 2 1

Sample Output 2



There are no comments at the moment.