## Editorial for DMOPC '15 Contest 2 P4 - Personal Assistant

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.**by cheesecake

This is a variation of the classical knapsack problem.

For subtasks and , let represent the maximum possible happiness value we can obtain if we only consider the -th minute and onward. Iterate backwards through the array, for each minute with an anime, we can either skip it or watch it. If anime is released on the -th minute, we have the transition formula .

For subtask , we need to realize that only the minutes with animes matter. The happiness value we can obtain from watching an anime can be found by greedily binary searching for the next anime we can watch if we watch this one. Implementation is left to the reader as an exercise.

Time Complexity:

## Comments