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 1 and 2, let dp[i] represent the maximum possible happiness value we can obtain if we only consider the i-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 j is released on the i-th minute, we have the transition formula dp[i] = max(dp[i+1], H[j] + dp[i+L[j]]).

For subtask 3, 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: \mathcal{O}(NlogN)


Comments

There are no comments at the moment.