DMOPC '14 Contest 6 P2 - GO Faster

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 129M

Problem type

As you look at a TTC map, you notice that some GO Train stations are beside a subway station, so you wonder whether it would be worthwhile to implement a high-frequency express train.

Knowing the number of passengers that get on and off at each subway station, determine the minimum and maximum number of riders for whom the express train will benefit - those who get on at the first stop and get off at the last stop.

Assume that both the subway line and the express train are eastbound only – that is, only from left to right. Also assume that the express train goes from the first to the last subway station, that no one gets off at the stop they get on, and that everyone gets off at the terminus.

Input Specification

The first line consists of N (2 \le N \le 100\,000), the number of subway stations.

The next N-1 lines contain two space-separated integers representing the number of passengers (up to 1000) getting on and off respectively. It is guaranteed that no one gets off at the first stop or gets on at the last stop, as the subway is eastbound only. There will never be a negative number of passengers on the train.

Output Specification

The output should consist of two lines containing the minimum and maximum number of passengers that will benefit respectively.

Sample Input

13 0
19 7
26 11

Sample Output


Explanation for Sample Output

Below is a diagram of the scenario:

As the subway reaches Plateau Crescent, it has 13 passengers. 7 get off, and since they boarded at Moccasin, they will not benefit from the express train. There are now 6 passengers who boarded at the first stop.

When it reaches Greenland Road, 11 people get off. In the best case, those 11 people boarded at Plateau but in the worst case, 6 of them boarded at Moccasin.

When it reaches Don Mills C.I., there are at most 6 and at least 0 people who will benefit from the express train as they boarded at Moccasin.




There are no comments at the moment.