概要

各木のりんご数 \(H_i\) のうち、基準 \(K\) 以上の木だけを合計できるとして、長さが \(M\) 以下の連続区間でその合計を最大化します。

考察

まず「出荷できるりんご」だけに注目します。区間 \((L,R)\) を選んだとき出荷されるのは、区間内で \(H_i \ge K\) を満たす木の \(H_i\) の総和です。ここで

• \(A_i = \begin{cases} H_i & (H_i \ge K) \\ 0 & (H_i < K) \end{cases}\)

と置くと、求めたい値は「長さ \(M\) 以下の連続部分配列における \(A_i\) の和の最大値」になります。

次に重要な気づきは \(A_i\) はすべて非負（\(0\) 以上） だという点です。非負なので、ある区間の和は、その区間を右や左に伸ばしても減りません。つまり、

• 「長さ \(\le M\) のどれか」よりも、可能なら長さを最大の \(M\) にした方が得（同じか増える）

となります（ただし \(M \ge N\) なら全体 \(1..N\) を取れる）。

よって、 - \(M \ge N\) なら全体の \(\sum A_i\) が答え - \(M < N\) なら 長さちょうど \(M\) の区間の和の最大値 を求めればよい

素朴に全区間を試すと区間数が \(O(NM)\) になり、\(N \le 10^6\) では到底間に合いません。そこで「長さ固定の区間和の最大」を \(O(N)\) で求める典型手法である スライディングウィンドウ を使います。

アルゴリズム

1. 各 \(H_i\) から \(A_i = (H_i \ge K ? H_i : 0)\) を作る（実装ではその場で変換する）。
2. ケース1: \(M \ge N\)
   • 全ての \(A_i\) を足した値を出力。
3. ケース2: \(M < N\)
   • 最初の \(M\) 個の和を window として作る。
   • 以降 \(i=M, M+1, \dots\) について、ウィンドウを1つ右にずらす：
     • 新しく入る値を加え、はみ出す古い値を引く
     • window の最大値を更新
   • 最終的な最大値を出力。

実装では、長さ \(M\) の直近要素を保持するために配列 buf をリングバッファとして使い、「はみ出す古い値」を \(O(1)\) で取り出しています。

（例） - \(H=[12, 5, 10, 3, 20],\ K=10 \Rightarrow A=[12,0,10,0,20]\) - \(M=3\) の長さ3区間和は - \([12,0,10]=22\) - \([0,10,0]=10\) - \([10,0,20]=30\) - 最大は \(30\)

計算量

• 時間計算量: \(O(N)\)（各要素を1回ずつ処理）
• 空間計算量: \(O(M)\)（スライディングウィンドウ用のバッファ）

実装のポイント

• \(N \le 10^6\) なので、Python では sys.stdin.buffer.read() を使った高速入力が有利です（コードはバイト列から整数を直接パース）。

• 合計は最大で \(10^9 \times 10^6 = 10^{15}\) 程度になり得ますが、Python の int なら問題ありません。

• \(M \ge N\) のときは「長さちょうど \(M\) の区間」が存在しないので、全体を取る分岐を入れて処理を簡潔にしています。

  ソースコード

import sys

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

it = ints_from_stdin()
N = next(it)
M = next(it)
K = next(it)

if M >= N:
    ans = 0
    for _ in range(N):
        h = next(it)
        if h >= K:
            ans += h
    sys.stdout.write(str(ans))
else:
    W = M
    buf = [0] * W
    window = 0
    max_sum = 0
    p = 0

    for i in range(N):
        h = next(it)
        a = h if h >= K else 0
        if i < W:
            buf[i] = a
            window += a
            if i == W - 1:
                max_sum = window
        else:
            old = buf[p]
            buf[p] = a
            window += a - old
            p += 1
            if p == W:
                p = 0
            if window > max_sum:
                max_sum = window

    sys.stdout.write(str(max_sum))

---

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