The Campus Bus
Submit solution
Points:
50
Time limit:
1.0s
Memory limit:
256M
Author:
Problem type
Allowed languages
C, C++
For an activity at the University of Puerto Rico at Mayagüez, a bus visits n stops in order. It is empty before the first stop. At stop i, a[i] passengers get off and then b[i] passengers get on.
Find the minimum capacity needed to carry everyone without exceeding it at any time. No passenger gets off unless already on the bus. At the final stop, all remaining passengers get off and nobody gets on.
Input
The first line contains n. Each of the next n lines contains a[i] and b[i], in stop order.
Output
Print one integer: the minimum required capacity.
Constraints
2 ≤ n ≤ 1 000; 0 ≤ a[i], b[i] ≤ 1 000. All inputs satisfy the conditions in the description.
Example
| Input Example | Output Example |
|---|---|
| 5 0 4 1 3 5 2 1 0 2 0 |
6 |
After each stop there are 4, 6, 3, 2 and 0 passengers.
Source
Adapted for OiPR 2026. Codeforces 116A — Tram.
Comments