Editorial for COCI '12 Contest 4 #1 Orehnjaca
Submitting an official solution before solving the problem yourself is a bannable offence.
Each spectator thought he would get pieces of walnut roll (that is how many pieces there are in total, marked from to ). The solution to the first part of the task is therefore determining the maximum value of 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 where we initialize every element to the value (every piece is in its place). For each spectator marked with , we sum up the values in the array marked from to ; also, in that interval, we change every value to (the piece is not there anymore). During this procedure, we keep the maximum value of the sum.
Comments