概要

「少なくとも1つ、長さ \(K\) の連続区間を必ず全部選ぶ」という制約のもとで、選んだ花壇の美しさ合計を最大化する問題です。
固定した必須区間の外側は「正の値だけ選ぶ」のが最適、という性質を使うと高速に解けます。

考察

重要な観察は次の2つです。

1. 必須で選ぶ連続区間 \([l, l+K-1]\) を1つ固定すると、その区間内は全て選ぶしかない。
2. その区間の外側（左側と右側）は自由に選べるので、
   
   • \(A_i > 0\) なら選ぶ
     
   • \(A_i \le 0\) なら選ばない
     が最適です（足しても得しないため）。

したがって、開始位置 \(l\) を固定したときの最適値は

[ \text{(左側の正の値の総和)} + \text{(区間 }[l,l+K-1]\text{ の総和)} + \text{(右側の正の値の総和)} ]

になります。

---

素朴にやると、各 \(l\) ごとに - 区間和を毎回 \(O(K)\) で計算 - 左右の正の和を毎回走査して計算

となり、最悪 \(O(N^2)\) 近くかかってしまい、\(N \le 5\times 10^5\) では間に合いません。

そこで累積和を使います。

• 通常の累積和 pref： [ \text{pref}[i] = A_1 + \cdots + A_i ] で区間和を \(O(1)\) 取得。
• 正の値のみの累積和 pos_pref： [ \text{pos_pref}[i] = \sum_{j=1}^{i}\max(A_j,0) ] で「ある範囲の正の値総和」を \(O(1)\) 取得。

これで各 \(l\) を \(O(1)\) で評価でき、全体 \(O(N)\) になります。

アルゴリズム

1. pref（通常の累積和）を作る。
2. pos_pref（\(\max(A_i,0)\) の累積和）を作る。
3. すべての開始位置 \(l=0..N-K\)（0-indexed）について：
   • \(r = l + K\)
   • 必須区間和
     [ \text{middle} = \text{pref}[r]-\text{pref}[l] ]
   • 左側の正の和
     [ \text{left_pos} = \text{pos_pref}[l] ]
   • 右側の正の和
     [ \text{right_pos} = \text{pos_pref}[N]-\text{pos_pref}[r] ]
   • 合計
     [ \text{total} = \text{left_pos} + \text{middle} + \text{right_pos} ]
   • 最大値を更新。
4. 最大値を出力。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 配列は 0-indexed で扱い、累積和は長さ \(N+1\) にすると区間和式が簡潔になります。

• 答えは負になる可能性があるので、初期値は十分小さい値（コードでは -10**30）にします。

• A_i が大きく、和も大きくなるため Python の int をそのまま使えば安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    # Prefix sums
    pref = [0] * (N + 1)
    for i in range(N):
        pref[i + 1] = pref[i] + A[i]

    # Positive contribution prefix: sum of max(A[i], 0)
    pos_pref = [0] * (N + 1)
    for i in range(N):
        pos_pref[i + 1] = pos_pref[i] + (A[i] if A[i] > 0 else 0)

    INF = 10**30
    ans = -INF

    # l: 0-based start of mandatory K consecutive selected flowerbeds
    for l in range(0, N - K + 1):
        r = l + K
        middle = pref[r] - pref[l]
        left_pos = pos_pref[l]
        right_pos = pos_pref[N] - pos_pref[r]
        total = left_pos + middle + right_pos
        if total > ans:
            ans = total

    print(ans)

if __name__ == "__main__":
    main()

---

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