Overview

This is a problem about a hiking course on a mountain trail, where you need to determine which checkpoint to stop at in order to maximize “total scenic score − total stamina cost.” You can solve it by incrementally computing the satisfaction and tracking its maximum value.

Analysis

Organizing the Problem

The satisfaction when finishing at checkpoint \(k\) is expressed by the following formula:

\[f(k) = \sum_{i=1}^{k} S_i - \sum_{i=1}^{k-1} C_i\]

We want to compute \(f(k)\) for all \(k\) (\(1 \leq k \leq N\)) and find the maximum value.

Key Insight: It Can Be Computed Incrementally

Let’s look at the relationship between \(f(k)\) and \(f(k+1)\):

\[f(k+1) = \sum_{i=1}^{k+1} S_i - \sum_{i=1}^{k} C_i = f(k) + S_{k+1} - C_k\]

In other words, if we know \(f(k)\), we can obtain \(f(k+1)\) simply by adding \(S_{k+1} - C_k\).

Concrete Example

For example, when \(N=4\), \(S = [10, 3, 8, 2]\), \(C = [5, 6, 1]\):

\(k\)	Satisfaction \(f(k)\)	Calculation
1	\(10\)	\(S_1 = 10\)
2	\(10 - 5 + 3 = 8\)	\(f(1) - C_1 + S_2\)
3	\(8 - 6 + 8 = 10\)	\(f(2) - C_2 + S_3\)
4	\(10 - 1 + 2 = 11\)	\(f(3) - C_3 + S_4\)

The maximum value is \(f(4) = 11\).

Comparison with the Naive Approach

Recomputing \(f(k)\) from scratch each time costs \(O(N^2)\), which would result in TLE for \(N \leq 10^6\). By updating incrementally, we can solve it in \(O(N)\).

Algorithm

1. Initialize \(\text{current} = S_1\) (satisfaction at checkpoint 1) and \(\text{best} = S_1\).
2. For \(i = 2, 3, \ldots, N\), do the following:
   • Update \(\text{current} = \text{current} - C_{i-1} + S_i\).
   • If \(\text{current} > \text{best}\), update \(\text{best} = \text{current}\).
3. Output the final \(\text{best}\).

This is a classic pattern of “tracking the maximum while scanning,” where we incrementally compute the satisfaction at each checkpoint while keeping track of the maximum value.

Complexity

• Time complexity: \(O(N)\) — just a single pass through the array
• Space complexity: \(O(N)\) — for storing the input arrays \(S\) and \(C\) (can be reduced to \(O(1)\) by reading input on the fly)

Implementation Notes

• Fast input with sys.stdin.read(): Since \(N\) can be as large as \(10^6\), in Python it is faster to read all input at once with sys.stdin.read() and then split() it, rather than calling input() repeatedly.

• Case \(N = 1\): The loop does not execute and best = S[0] directly becomes the answer, so no special case handling is needed.

• Overflow: Since \(S_i, C_i\) can be up to \(10^9\) and \(N\) up to \(10^6\), the satisfaction can reach approximately \(10^{15}\). However, this is not an issue in Python since it handles arbitrary-precision integers.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    S = [int(input_data[idx + i]) for i in range(N)]; idx += N
    C = [int(input_data[idx + i]) for i in range(N - 1)]; idx += N - 1

    current = S[0]
    best = current
    for i in range(1, N):
        current = current - C[i - 1] + S[i]
        if current > best:
            best = current
    print(best)

main()

---

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