概要

チェックポイント \(k\) で終了したときの満足度 \( \left(\sum_{i=1}^{k} S_i\right) - \left(\sum_{i=1}^{k-1} C_i\right)\) を、\(k\) を最適に選んで最大化する問題です。

考察

満足度を \(k\) ごとにそのまま計算すると、各 \(k\) について和を取り直すことになり、素朴には \(O(N^2)\) かかってしまいます。\(N \le 10^6\) なのでこれは確実に TLE になります。

ここで重要な気づきは、「\(k\) を 1 つ進めたときに満足度がどう変化するか」を見ることです。

• \(k=1\) の満足度は \(S_1\)
• \(k\) から \(k+1\) に進むとき
  • 新たに景観スコア \(S_{k+1}\) を得る
  • 移動コスト \(C_k\) を払う

したがって満足度の増分は \(+S_{k+1} - C_k\) です。
つまり、満足度は「前の満足度に \(S_{k} - C_{k-1}\) を足していく累積値」として、1 回の走査で更新できます。

あとは「途中で終了してよい」ので、走査中に現れた満足度の最大値を答えにすればよいです。

具体例： - \(S=[10, 3, 8]\), \(C=[5, 100]\) - \(k=1\): \(10\) - \(k=2\): \(10 + 3 - 5 = 8\) - \(k=3\): \(8 + 8 - 100 = -84\) 最大は \(10\)（最初でやめるのが最適）
このように「累積しながら最大を取る」だけで済みます。

アルゴリズム

1. \(val \leftarrow S_1\)（\(k=1\) の満足度）
2. \(best \leftarrow val\)
3. \(k=2\) から \(N\) まで順に：
   • 直前の移動コストは \(C_{k-1}\)
   • \(val \leftarrow val + S_k - C_{k-1}\)
   • \(best \leftarrow \max(best, val)\)
4. \(best\) を出力

これは \(k\) ごとの満足度を「前からの累積」で求め、同時に最大値を更新する方法です。

計算量

• 時間計算量: \(O(N)\)（1 回の走査）
• 空間計算量: \(O(N)\)（提示コードでは \(S\) を保持するため。工夫すれば \(O(1)\) も可能）

実装のポイント

• \(N=1\) のときはコスト配列が入力されないため、特別に \(S_1\) をそのまま出力します。

• \(S_i, C_i \le 10^9\) で \(N \le 10^6\) なので、累積値は最大で \(10^{15}\) 程度になり得ます。Python の int は多倍長なので問題ありませんが、配列に入れるなら 64bit 整数相当（コードでは array('q')）が安全です。

• 入力が大きいので、高速化のために sys.stdin.buffer.read() でまとめて読み取り、整数をパースしています（通常の input() だと遅くなりやすい）。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。