Overview

This is a simulation problem where a bus visits stops in order, and passengers board and alight at each stop. We need to find the number of passengers after boarding is complete at the final stop.

Approach

This problem can be solved by simply simulating the process at each stop in order.

The process at each stop \(i\) is as follows: 1. \(A_i\) passengers board → passengers += A_i 2. If \(i \leq N-1\), \(\min(\text{current number of passengers}, B_i)\) passengers alight

Let’s think about the “alighting” process. The fact that \(\min(\text{current number of passengers}, B_i)\) passengers alight means: - When the number of passengers \(\geq B_i\) → \(B_i\) passengers alight, and the remainder is passengers - B_i - When the number of passengers \(< B_i\) → everyone alights, and the remainder is \(0\)

This can be written in one line as passengers = max(0, passengers - B_i).

Concrete example: For \(N = 3\), \(A = [5, 3, 2]\), \(B = [2, 4]\):

The answer is \(4\).

Since this problem only requires processing each stop once, a straightforward simulation is sufficiently fast. No special algorithm is needed.

Algorithm

1. Initialize passengers to \(0\).
2. For stops \(1\) through \(N-1\), repeat the following in order:
   • Add \(A_i\) (boarding).
   • Set passengers = max(0, passengers - B_i) (alighting).
3. At the last stop \(N\), only add \(A_N\) (no alighting).
4. Output passengers.

Complexity

• Time complexity: \(O(N)\) — since each stop is processed exactly once
• Space complexity: \(O(1)\) — only a variable to hold the number of passengers is used (no array needed since input can be read on the fly)

Implementation Notes

• Pay attention to the input format. For stops \(1\) through \(N-1\), each line contains two values \(A_i\) and \(B_i\), while the line for the last stop \(N\) contains only a single value \(A_N\).

• Use max(0, passengers - B_i) to prevent the number of passengers from becoming negative during alighting. Simply writing passengers -= B_i may result in a negative number of passengers, leading to WA.

• Since \(A_i\) and \(B_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the number of passengers can reach approximately \(2 \times 10^{14}\). In Python, there is no need to worry about integer overflow, but in C++ and similar languages, you need to use long long.

  Source Code

N = int(input())
passengers = 0
for i in range(N - 1):
    a, b = map(int, input().split())
    passengers += a
    passengers = max(0, passengers - b)
a = int(input())
passengers += a
print(passengers)

This editorial was generated by claude4.6opus-thinking.