Overview

Given scenery scores and travel costs for each checkpoint, the problem asks you to choose an appropriate ending point to maximize satisfaction (the cumulative sum of scenery scores minus the cumulative sum of travel costs).

Analysis

The satisfaction at each checkpoint \(k\) can be calculated as \((\sum_{i=1}^{k} S_i) - (\sum_{i=1}^{k-1} C_i)\). A naive approach would be to compute the satisfaction for every \(k\) and find the maximum value. However, since \(N\) can be as large as \(10^6\), computing the sums from scratch each time without precomputing prefix sums would result in a time complexity of \(O(N^2)\), which would not meet the time limit.

In this problem, we can solve it efficiently by progressing sequentially from checkpoint 1 while updating the current satisfaction along the way. The satisfaction at each point can be computed by adding the current scenery score \(S_i\) to and subtracting the travel cost \(C_{i-1}\) from the satisfaction at the previous point, yielding a time complexity of \(O(N)\).

Algorithm

1. Set the satisfaction at checkpoint 1, \(S_1\), as the initial value
2. Process checkpoints from 2 to N in order:
   • Current satisfaction = previous satisfaction + \(S_i\) - \(C_{i-1}\)
   • Update the maximum if the current satisfaction exceeds it
3. Output the resulting maximum satisfaction

This approach leverages the fact that the satisfaction can be expressed as a recurrence relation. Specifically, the satisfaction \(F(k)\) at checkpoint \(k\) can be computed as \(F(k) = F(k-1) + S_k - C_{k-1}\) (with \(F(1) = S_1\)).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Read and process all input data at once

• When \(N=1\), there are no travel costs, so it requires special handling

• Process everything in a single loop while maintaining the current satisfaction and maximum satisfaction in variables

• Do not forget to check for maximum value updates at each step

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    S = list(map(int, data[1:1+n]))
    if n == 1:
        print(S[0])
        return
        
    C = list(map(int, data[1+n:1+n+(n-1)]))
    
    current_sum = S[0]
    max_satisfaction = current_sum
    
    for i in range(1, n):
        current_sum = current_sum + S[i] - C[i-1]
        if current_sum > max_satisfaction:
            max_satisfaction = current_sum
            
    print(max_satisfaction)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.