Overview

Given a mountain trail where each checkpoint has a scenery score and a movement cost, find the maximum “satisfaction” obtainable when you can end the hike at any point along the way.

Analysis

In this problem, we want to choose an ending point \(k\) that maximizes the satisfaction, defined as the total score from checkpoint \(1\) to \(k\) minus the total movement cost to travel from checkpoint \(1\) to checkpoint \(k\).

Satisfaction is defined as follows: $\( \text{satisfaction}(k) = \left(\sum_{i=1}^{k} S_i\right) - \left(\sum_{i=1}^{k-1} C_i\right) \)$

A naive approach that computes the above sums for every \(k\) from scratch would result in a time complexity of \(O(N^2)\), which is too slow for the constraint \(N \leq 10^6\) (TLE).

However, upon closer inspection of the satisfaction formula, we can notice that it can be computed efficiently using prefix sums. That is, by scanning from left to right while maintaining the running total of scores and the running total of costs up to the current position, we avoid recalculating the sums each time.

Also, when \(k = 1\), no movement occurs, so the satisfaction is simply \(S_1\).

Therefore, by using the prefix sum approach, we can solve the problem in \(O(N)\) time complexity.

Algorithm

1. First, set the initial maximum value to the satisfaction at \(k = 1\), which is \(S_1\).
2. Prepare variables to maintain the prefix sum of scores \(current\_sum\_S\) and the prefix sum of costs \(current\_sum\_C\), initializing them to \(S_1\) and \(0\), respectively.
3. Loop from \(k = 2\) to \(N\), performing the following:
   • Add \(S_k\) to \(current\_sum\_S\).
   • Add \(C_{k-1}\) to \(current\_sum\_C\).
   • Compute the current satisfaction \(current\_sum\_S - current\_sum\_C\).
   • If it is greater than the current maximum, update the maximum.
4. Output the maximum value at the end.

By doing this, we can efficiently compute the satisfaction for all possible ending points and find the maximum among them.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input)

Implementation Notes

• By maintaining prefix sums in variables and updating them incrementally, we avoid recalculating the sums each time.

• Be careful with the handling of 1-indexed vs. 0-indexed indices (e.g., array subscripts).

• sys.stdin.read is used to speed up input reading.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    S = list(map(int, data[1:N+1]))
    C = list(map(int, data[N+1:N*2]))
    
    # 満足度: (S[0] + ... + S[k-1]) - (C[0] + ... + C[k-2])
    # k=1 のとき、満足度は S[0]
    
    max_satisfaction = S[0]
    current_sum_S = S[0]
    current_sum_C = 0
    
    for k in range(2, N+1):
        current_sum_S += S[k-1]
        current_sum_C += C[k-2]
        satisfaction = current_sum_S - current_sum_C
        if satisfaction > max_satisfaction:
            max_satisfaction = satisfaction
            
    print(max_satisfaction)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.