Overview

This problem asks you to maximize the satisfaction when finishing at checkpoint \(k\): \( \left(\sum_{i=1}^{k} S_i\right) - \left(\sum_{i=1}^{k-1} C_i\right)\), by choosing \(k\) optimally.

Analysis

If we compute the satisfaction directly for each \(k\), we would need to recalculate the sums for every \(k\), which naively takes \(O(N^2)\). Since \(N \le 10^6\), this would certainly result in TLE.

The key insight here is to look at “how the satisfaction changes when we advance \(k\) by one.”

• The satisfaction for \(k=1\) is \(S_1\)
• When advancing from \(k\) to \(k+1\):
  • We gain the new scenic score \(S_{k+1}\)
  • We pay the travel cost \(C_k\)

Therefore, the increment in satisfaction is \(+S_{k+1} - C_k\).
In other words, the satisfaction can be updated as “a cumulative value where we add \(S_{k} - C_{k-1}\) to the previous satisfaction,” computed in a single pass.

Since “we may stop at any point along the way,” we simply take the maximum satisfaction encountered during the scan as our answer.

Concrete example: - \(S=[10, 3, 8]\), \(C=[5, 100]\) - \(k=1\): \(10\) - \(k=2\): \(10 + 3 - 5 = 8\) - \(k=3\): \(8 + 8 - 100 = -84\) The maximum is \(10\) (stopping at the first checkpoint is optimal).
As shown, all we need to do is “take the maximum while accumulating.”

Algorithm

1. \(val \leftarrow S_1\) (satisfaction for \(k=1\))
2. \(best \leftarrow val\)
3. For \(k=2\) to \(N\) in order:
   • The previous travel cost is \(C_{k-1}\)
   • \(val \leftarrow val + S_k - C_{k-1}\)
   • \(best \leftarrow \max(best, val)\)
4. Output \(best\)

This computes the satisfaction for each \(k\) as a “cumulative value from the start” and simultaneously updates the maximum.

Complexity

• Time complexity: \(O(N)\) (a single pass)
• Space complexity: \(O(N)\) (because the provided code stores \(S\); with some optimization, \(O(1)\) is also possible)

Implementation Notes

• When \(N=1\), the cost array is not given as input, so we handle this as a special case by directly outputting \(S_1\).

• Since \(S_i, C_i \le 10^9\) and \(N \le 10^6\), the cumulative value can reach up to around \(10^{15}\). Python’s int supports arbitrary precision so there is no issue, but if storing values in an array, using the equivalent of 64-bit integers (array('q') in the code) is safe.

• Since the input is large, we read everything at once using sys.stdin.buffer.read() and parse the integers for speed optimization (using the standard input() tends to be slower).

  Source Code

import sys
from array import array

def ints_from_stdin():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num

def main():
    it = ints_from_stdin()
    try:
        N = next(it)
    except StopIteration:
        return

    S = array('q')
    for _ in range(N):
        S.append(next(it))

    if N == 1:
        sys.stdout.write(str(S[0]))
        return

    val = S[0]
    best = val
    for idx in range(1, N):
        c = next(it)
        val += S[idx] - c
        if val > best:
            best = val

    sys.stdout.write(str(best))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.