Overview

Define “satisfaction” as the “sum of scenic scores” minus the “sum of movement costs” from checkpoint \(1\) to checkpoint \(k\), and find its maximum value.

Analysis

First, let \(f(k)\) denote the satisfaction when the hike ends at checkpoint \(k\), and let’s organize the formulas.

• When \(k=1\): \(f(1) = S_1\)
• When \(k=2\): \(f(2) = (S_1 + S_2) - C_1\)
• When \(k=3\): \(f(3) = (S_1 + S_2 + S_3) - (C_1 + C_2)\)

Computing the total from scratch for each \(k\) takes \(O(k)\) time per \(k\). If we compute this for all \(k\) (from \(1\) to \(N\)), the overall time complexity becomes \(O(N^2)\), which will not fit within the time limit given the constraint \(N \leq 10^6\).

Now, let’s focus on the difference in satisfaction between adjacent checkpoints. Comparing \(f(k)\) and \(f(k-1)\), we find the following relationship: $\(f(k) = f(k-1) + S_k - C_{k-1}\)\( In other words, "the satisfaction at checkpoint \)k\(" can be obtained by simply adding "the newly gained score \)Sk\(" to "the satisfaction at the previous checkpoint \)k-1\(" and subtracting "the movement cost \)C{k-1}$“.

By utilizing this property, we can compute the next state from the previous state in \(O(1)\), making it possible to solve the problem in \(O(N)\) total time.

Algorithm

1. Prepare a variable max_satisfaction to hold the maximum satisfaction and a variable current_satisfaction to hold the satisfaction at the current checkpoint. Initialize both to \(S_1\).
2. Repeat the following operations for \(i = 2\) to \(N\) in order:
   • Add \(S_i\) to current_satisfaction and subtract \(C_{i-1}\).
   • Compare max_satisfaction with current_satisfaction, and update max_satisfaction with the larger value.
3. Output the final value of max_satisfaction.

Complexity

• Time complexity: \(O(N)\)
  • Since we scan through the \(N\) checkpoints once, the processing completes in time proportional to \(N\), including input reading.
• Space complexity: \(O(N)\)
  • Memory proportional to \(N\) is used to store the input scenic scores \(S_i\) in a list. (This can be reduced to \(O(1)\) with some ingenuity.)

Implementation Notes

• Handling large input: Since \(N=10^6\) and the input is very large, in Python it is advisable to read input quickly using sys.stdin.read().split() or generators.

• Setting the initial value: Since the case \(k=1\) is the minimal configuration, the initial value for the maximum should be set to \(S_1\), not \(0\).

• Types: The cumulative sums of scores and costs can become very large values (up to about \(10^{15}\)), but since Python natively supports arbitrary-precision integers, there is no concern about overflow.

  Source Code

import sys
import itertools

def solve():
    # 標準入力からトークン（数値）を1つずつ取得するジェネレータ
    tokens = (token for line in sys.stdin for token in line.split())
    
    # チェックポイントの数 N を取得
    try:
        n_str = next(tokens)
    except StopIteration:
        return
    
    n = int(n_str)
    
    # 景観スコア S_1, S_2, ..., S_N を読み込む
    # 体力コスト C_i が後に続くため、S はリストに格納する必要がある
    s = list(map(int, itertools.islice(tokens, n)))
    
    if not s:
        return
    
    # ハイキングの満足度の最大値を管理する変数
    # 初期値はチェックポイント1で終了した場合の満足度 S_1
    max_satisfaction = s[0]
    current_satisfaction = s[0]
    
    # 残りのトークンは体力コスト C_1, C_2, ..., C_{N-1}
    costs = map(int, tokens)
    
    # チェックポイント k = 2 から N まで順番に満足度を計算
    # チェックポイント k での満足度 f(k) は、f(k-1) + S_k - C_{k-1} で求められる
    # enumerate(costs, 1) により、i は 1 から始まり、s[i] は S_{i+1} に対応する
    for i, cost in enumerate(costs, 1):
        if i >= n:
            break
        # 現在の満足度を更新：前のチェックポイントまでの満足度 + 次の景観スコア - 移動コスト
        current_satisfaction += s[i] - cost
        # 最大値を更新
        if current_satisfaction > max_satisfaction:
            max_satisfaction = current_satisfaction
            
    # 結果を出力
    sys.stdout.write(str(max_satisfaction) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.