Overview

This is a simulation problem where you serve \(N\) visitors in order at a reception counter and need to find the time when service for the last visitor finishes.

Analysis

The key to this problem is understanding how the service start time \(S_i\) for each visitor is determined.

Service for visitor \(i\) begins at the moment both of the following conditions are satisfied: 1. Service for the previous visitor \(i-1\) has finished (the counter is free) 2. Visitor \(i\) has already arrived

In other words, the service start time is:

\[S_i = \max(S_{i-1} + B_{i-1},\ A_i)\]

Understanding with a concrete example

For example, consider \(N = 3\) with the following input:

Visitor	Arrival time \(A_i\)	Service time \(B_i\)
1	0	5
2	3	3
3	10	2

• Visitor 1: Arrives at time \(0\), service starts at \(S_1 = 0\), service ends at \(0 + 5 = 5\)
• Visitor 2: Arrived at time \(3\), but the counter is occupied until time \(5\) → \(S_2 = \max(5, 3) = 5\), service ends at \(5 + 3 = 8\)
• Visitor 3: Arrives at time \(10\), the counter is free at time \(8\) → \(S_3 = \max(8, 10) = 10\), service ends at \(10 + 2 = 12\)

The answer is \(12\). Like visitor 2, when “the visitor has arrived but the counter is not free,” they wait. Like visitor 3, when “the counter is free but the visitor hasn’t arrived yet,” the counter waits for the visitor’s arrival.

Is a straightforward approach sufficient?

This problem can be solved by simply computing the recurrence from front to back. Since each visitor requires \(O(1)\) computation, no special optimization is needed.

Algorithm

We use a variable \(S\) to track “the time when the counter becomes free (= the service end time for the previous visitor).”

1. Initialize \(S = 0\) (the counter is available from time \(0\))
2. For each visitor \(i\):
   • The service start time is \(\max(S, A_i)\) (the later of when the counter becomes free and the arrival time)
   • The service end time is \(\max(S, A_i) + B_i\)
   • Update \(S\) to this service end time
3. After processing all visitors, \(S\) is the answer

When written as code, the update inside the loop is just a single line:

S = max(S, A) + B

Complexity

• Time complexity: \(O(N)\) — \(O(1)\) processing for each visitor, repeated \(N\) times
• Space complexity: \(O(1)\) — only the variable \(S\) is needed (excluding input reading)

Implementation Notes

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

• The variable \(S\) represents “the time when the counter becomes free.” By setting its initial value to \(0\) (the counter is free from the start), even visitor 1 can be handled uniformly with the same formula S = max(S, A) + B.

  Source Code

N = int(input())
S = 0
for _ in range(N):
    A, B = map(int, input().split())
    S = max(S, A) + B
print(S)

---

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