Editorial for DMOPC '15 Contest 2 P4 - Personal Assistant
Submitting an official solution before solving the problem yourself is a bannable offence.
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.