Editorial for COCI '10 Contest 1 #2 Profesor
Submitting an official solution before solving the problem yourself is a bannable offence.
Observe that checking every possible interval and every possible grade is too slow for a sufficiently large
To obtain a complete score, we need another approach.
If we assume the grade which the professor will award the students, we can, in a single pass, determine the longest continuous subsequence of desks such that each desk contains at least one student deserving the assumed grade. This can be implemented using a counter storing the current number of continuous desks, and updating it for each desk.
Finally, the solution consists of iterating the described algorithm for each grade from
Also observe that the problem can be solved with complexity
Comments