Editorial for DMOPC '14 Contest 3 P6 - Not Enough Time!
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
This is extremely similar to the standard 0-1 knapsack problem (you can Google it). The only modification we need to do is to consider the Poor, Average, and Good problemsets simultaneously instead of sequentially. A direct approach to this will get 50% of the points because of memory limits. To reduce the memory footprint, you should realize that only the current row and the previous row of the dp state matter, so you can use memory instead of
memory.
Time Complexity:
Comments