Editorial for COCI '12 Contest 4 #1 Orehnjaca


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.

Each spectator thought he would get K-P+1 pieces of walnut roll (that is how many pieces there are in total, marked from P to K). The solution to the first part of the task is therefore determining the maximum value of K-P+1 which we calculate for each spectator individually.

As spectators were taking pieces of the walnut roll, at some point it might have occurred that a spectator could not take a piece that was provided for them because someone else had taken it already. We therefore create an array of a maximum length of 1000 where we initialize every element to the value 1 (every piece is in its place). For each spectator marked with i, we sum up the values in the array marked from P_i to K_i; also, in that interval, we change every value 1 to 0 (the piece is not there anymore). During this procedure, we keep the maximum value of the sum.


Comments

There are no comments at the moment.