概要

長さ \(W\) の連続部分列ごとに「区間和 \(+\;K \times\) 区間最小値」を計算し、その最大値を求めます。全区間を高速に処理するために、区間和はスライド更新、区間最小値は単調キューで管理します。

考察

各 \(l\) に対して評価値は $\(\left(\sum_{i=l}^{l+W-1} A_i\right) + K \times \min(A_l,\ldots,A_{l+W-1})\)\( です。つまり、各長さ \)W$ の窓（スライディングウィンドウ）について

• 区間の 総和
• 区間の 最小値

が分かれば評価値はすぐ計算できます（\(K\) が負でも式は同じで、最小値の取り方自体は変わりません）。

素朴解が遅い理由

全ての \(l\) について - 和を毎回 \(W\) 個足す（\(O(W)\)） - 最小値を毎回 \(W\) 個から探す（\(O(W)\)）

をすると、合計で \(O(NW)\) になり、最大で \(5\times 10^5\) に対して間に合いません。

どう解決するか

• 区間和は「右端を 1 つ追加、左端を 1 つ削除」で \(O(1)\) 更新できる。
• 区間最小値は「単調増加な deque（単調キュー）」を使うと、各要素が高々 1 回入って 1 回出るので全体 \(O(N)\) で求められる。

例：\(A=[3,1,4,2],\;W=3\)
窓は \([3,1,4]\)（最小 \(1\)）, \([1,4,2]\)（最小 \(1\)）。
最小値を毎回探す代わりに、最小になり得ない大きい要素を deque の末尾から捨てていくことで、先頭が常に最小値になるよう保てます。

アルゴリズム

1. 左から順に \(i=0..N-1\) を処理する。
2. 区間和 \(s\) を更新：
   • \(s \leftarrow s + A[i]\)
   • もし \(i \ge W\) なら、窓から外れる \(A[i-W]\) を引いて \(s \leftarrow s - A[i-W]\)
3. 区間最小値を管理する deque dq（要素は「添字」）を更新：
   • deque 内の値 \(A[dq]\) が 単調増加 になるように保つ。
   • 新しい要素 \(A[i]\) を入れる前に、末尾から $\(A[dq[-1]] \ge A[i]\)$ を満たす間は pop()（末尾の方が大きいなら、今後最小になれないため）。
   • その後 dq.append(i)。
4. deque の先頭が窓の外に出たら削除：
   • 窓は \([i-W+1,\,i]\)（\(i \ge W-1\) のとき）なので、 $\(dq[0] \le i-W\)$ なら popleft()。
5. \(i \ge W-1\) なら窓が完成しているので評価値を計算：
   • 最小値は \(A[dq[0]]\)
   • 評価値 \(val = s + K \times A[dq[0]]\)
   • 最大値を更新

これで全ての窓を 1 回ずつ処理できます。

計算量

• 時間計算量: \(O(N)\)（各要素は deque に高々 1 回入って 1 回出る）
• 空間計算量: \(O(W)\)（deque に最大で窓サイズ程度の要素が入る）

実装のポイント

• deque には「値」ではなく「添字」を入れると、窓の外判定（\(i-W\) との比較）が簡単です。

• 単調キューの更新は

  • 末尾から「大きい（または等しい）」ものを捨てる（>= を使う）
  • 先頭から窓外を捨てる の順で行うと安定します。

• \(K\) や \(A_i\) が負でも処理は同じで、評価値計算の式をそのまま適用すればOKです。

• Python では入力が大きいので sys.stdin.buffer.read() を使うと高速です。

  ソースコード

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, W, K = data[0], data[1], data[2]
    A = data[3:3+N]

    dq = deque()  # indices, A[dq] increasing
    s = 0
    ans = None

    for i, x in enumerate(A):
        s += x
        if i >= W:
            s -= A[i - W]

        while dq and A[dq[-1]] >= x:
            dq.pop()
        dq.append(i)

        while dq[0] <= i - W:
            dq.popleft()

        if i >= W - 1:
            val = s + K * A[dq[0]]
            if ans is None or val > ans:
                ans = val

    print(ans)

if __name__ == "__main__":
    main()

---

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