Overview

In a \(N\)-day trip, we process daily income and expenses in order, and find the minimum initial amount of money \(X\) such that the amount of money at the end of each day is always \(0\) or more.

Analysis

Key Insight

The amount of money immediately after all processing on day \(i\) is complete can be expressed using the initial amount \(X\) and the cumulative sum of the daily net income/expenses.

Writing the amount of money after day \(i\) as a formula:

\[X + \sum_{k=1}^{i}(A_k - B_k)\]

Here, if we define the cumulative sum \(C_i\) as \(\sum_{k=1}^{i}(A_k - B_k)\), then the amount of money after day \(i\) is \(X + C_i\).

Organizing the Conditions

For all \(i\) \((1 \leq i \leq N)\), the condition \(X + C_i \geq 0\) must hold.

Rearranging this:

\[X \geq -C_i \quad (\text{for all } i)\]

In other words, \(X\) must be at least the maximum of \(-C_i\).

\[X \geq \max_{1 \leq i \leq N}(-C_i) = -\min_{1 \leq i \leq N}(C_i)\]

Additionally, since there is also the condition \(X \geq 0\), the answer is:

\[X = \max\left(0, \; -\min_{1 \leq i \leq N}(C_i)\right)\]

Concrete Example

For example, with \(N = 3\), initial amount \(X\), and daily net income/expenses \((A_i - B_i) = (-3, +5, -4)\):

Day	\(C_i\) (cumulative sum)	Amount after day
1	\(-3\)	\(X - 3\)
2	\(+2\)	\(X + 2\)
3	\(-2\)	\(X - 2\)

The minimum cumulative sum is \(C_1 = -3\), so \(X \geq -(-3) = 3\) is required. Therefore, \(X = 3\) is the answer.

Algorithm

1. Compute the cumulative sum of daily net income/expenses \(A_i - B_i\) sequentially.
2. Track the minimum cumulative sum \(\min_{1 \leq i \leq N}(C_i)\).
3. The answer is \(\max(0, -\min_{1 \leq i \leq N}(C_i))\).

All of this can be processed simultaneously in a single loop.

Complexity

• Time complexity: \(O(N)\) — We only process each day’s net income/expenses once
• Space complexity: \(O(1)\) — We only use variables to store the cumulative sum and the minimum value

Implementation Notes

• The initial value of the minimum cumulative sum min_cumsum is set to \(0\). This corresponds to the fact that “if the cumulative sum never becomes negative, \(X = 0\) is sufficient” (in \(\max(0, -\min\_cumsum)\), \(0\) is selected).

• Since \(A_i, B_i\) can be up to \(10^9\) and \(N\) can be up to \(10^5\), the cumulative sum can reach approximately \(\pm 10^{14}\). Since Python does not have integer overflow, no special handling is needed.

  Source Code

N = int(input())
min_cumsum = 0
cumsum = 0
for _ in range(N):
    a, b = map(int, input().split())
    cumsum += a - b
    if cumsum < min_cumsum:
        min_cumsum = cumsum
X = max(0, -min_cumsum)
print(X)

---

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