Editorial for DMOPC '15 Contest 6 P3 - Harvest


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.

Since we only need to know the final number of potatoes in each row after the updates, we can use a difference array of length N to keep track of the number of potatoes in each row. Each column can be updated in O(1) time, making this part of the algorithm O(M). After retrieving the actual values, we can use a two-pointer approach to find the minimum W required in O(N) time. The total time complexity is therefore O(N+M).


Comments

There are no comments at the moment.