Overview

This is a problem where boarding and alighting occur at each bus stop during a bus tour, and we need to find the number of passengers on the bus at the end.

Analysis

In this problem, the following operations are performed at each bus stop: 1. \(A_i\) new passengers board. 2. When heading to the next stop, up to \(B_i\) passengers alight (however, if this exceeds the current number of passengers, everyone alights).

Therefore, we need to perform a simulation that processes boarding → alighting in order while tracking the “current number of passengers” at each step.

A straightforward approach would be to simply simulate by adding and subtracting the number of people each time. Since the constraints are large (\(N\) is up to \(2 \times 10^5\)), we need \(O(N)\) overall processing. However, since the number of passengers can be on the order of \(10^9\), and each simulation step can be done in constant time, this runs well within the time limit.

The key points are: performing the alighting after boarding, and using \(\min\) to ensure the number of alighting passengers does not exceed the current number of passengers.

Ultimately, we just need to output the number of passengers after boarding is completed at stop \(N\).

Algorithm

1. Read the boarding count \(A_i\) and alighting count \(B_i\) for each stop.
2. Prepare a variable current_passengers and initialize it to \(0\).
3. For each stop \(i = 1\) to \(N - 1\), repeat the following:
   • Add \(A_i\) (boarding)
   • Subtract \(\min(\text{current\_passengers}, B_i)\) (alighting)
4. At the final stop \(N\), add \(A_N\) (no alighting)
5. Output current_passengers

By simulating in order like this, we can obtain the answer.

Example

For instance, given the following input:

3
2 1
3 2
1

• Stop 1: 2 board → 1 alights → 1 remaining
• Stop 2: 3 board → 4 total → 2 alight → 2 remaining
• Stop 3: 1 boards → 3 total (this is the answer)

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for storing arrays \(A\) and \(B\))

Implementation Notes

• Processing at each stop should be done in the order “boarding → alighting”.

• Use \(\min\) to ensure the number of alighting passengers does not exceed the current number of passengers.

• Note that there is no alighting at the last stop.

  Source Code

N = int(input())
A = [0] * N
B = [0] * (N - 1)

for i in range(N - 1):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

A[N - 1] = int(input())

current_passengers = 0

for i in range(N - 1):
    current_passengers += A[i]
    current_passengers -= min(current_passengers, B[i])

current_passengers += A[N - 1]

print(current_passengers)

---

This editorial was generated by qwen3-coder-480b.