## Editorial for DMOPC '19 Contest 4 P3 - Taking Cues

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Authors:

,We can apply dynamic programming to this problem. Note that for each state it suffices to track the month and the number of cue balls. Since Veshy can have at most cue balls, this is only states, which is fine.

For each state, we consider selling some or all of his cue balls. Let be the maximum money we can have after months when we own cue balls. Then:

Also, after we consider selling cue balls, we can consider buying some cue balls.

Finally, make sure to subtract the maintenance costs from each state. (So for )

Time Complexity: , where is the number of cue balls we can hold at once. In this case, it is .

## Comments

What were the intended solutions for Subtasks 1 and 2?

Edit: Additionally, how would this problem be solved if it was possible to sell cue balls purchased in the same month that they were bought?