Editorial for DMOPC '14 Contest 6 P2 - GO Faster - Olympiads Online Judge

Editorial for DMOPC '14 Contest 6 P2 - GO Faster

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.

Author: Phoenix1369

The idea behind this problem is simply to keep track of a few numbers. To calculate the minimum $mi$ $m i$ , continuously subtract the number of people getting off from $S$ $S$ , the starting number of passengers. The result is $\max(mi, 0)$ $max (m i, 0)$ . The maximum number of people to benefit from the express train is $S$ $S$ - the sum of the minimum number of people getting off at each stop that must be from the first stop.

Time Complexity: $\mathcal{O}(N)$ $O (N)$

Comments

There are no comments at the moment.