概要

各日「働く(1)／休む(0)」を選ぶ長さ \(N\) の列を作り、連続勤務は \(K-1\) 日以下・連続休日は \(M-1\) 日以下という制約の下で、働いた日の給料合計を最大化します。

考察

重要な気づき

制約は「同じ状態（勤務／休日）が連続できる最大長」が決まっているだけなので、最適解は - 「最後に休んだ日」から「今日まで連続で働く」 - 「最後に働いた日」から「今日まで連続で休む」 という“直前の切り替え位置”だけを見れば遷移できます。

素朴なDPがなぜ間に合わないか

例えば - \(dp[i][x][c]\) = \(i\) 日目まで見て、状態 \(x\in\{0,1\}\) が連続 \(c\) 日続いているときの最大値
のように連続長 \(c\) を持つDPをすると、状態数が \(O(N(K+M))\) になり、\(N\le 2\times 10^5\) では到底間に合いません。

どう解決するか

「連続長」を明示的に持たずに、 - 最後が勤務で終わる最大値 \(dp1[i]\) - 最後が休日で終わる最大値 \(dp0[i]\) だけを持ち、遷移で “直前の切り替え日 \(p\)” を全探索する形にします。

ただしそのままだと - \(dp1[i]\) は \(p\in[i-K+1,\,i-1]\) の最大 - \(dp0[i]\) は \(p\in[i-M+1,\,i-1]\) の最大
を毎回求めることになり \(O(NK)\) や \(O(NM)\) になってしまいます。

そこで「スライドする区間最大」を 単調キュー（deque） で管理して、各 \(i\) を \(O(1)\) 償却で処理します。

アルゴリズム

DPの定義

\(i\) 日目まで（\(1\sim i\) 日）決めたとき： - \(dp1[i]\)：\(i\) 日目が 勤務 で終わるときの最大給料 - \(dp0[i]\)：\(i\) 日目が 休日 で終わるときの最大給料

初期状態として「0日目」を用意し、 - \(dp0[0]=0,\ dp1[0]=0\) とします（最初に勤務を始める／休みを始める両方を自然に扱うため）。

不可能な状態は \(-\infty\) とします（コードでは INF_NEG）。

遷移（勤務で終わる）

\(i\) 日目が勤務で終わるなら、直前に休日で終わった日を \(p\) とすると、 - \(p+1, p+2, \dots, i\) が連続勤務 - 連続勤務日数 \(i-p \le K-1\) より \(p \ge i-K+1\) - 連続勤務は1日以上なので \(p \le i-1\)

よって [ dp1[i] = \max{p\in[i-K+1,\,i-1]} \left(dp0[p] + \sum{t=p+1}^{i} A_t\right) ]

ここで累積和 \(pref[i]=\sum_{t=1}^{i}A_t\) を使うと [ \sum_{t=p+1}^{i} At = pref[i]-pref[p] ] なので [ dp1[i] = pref[i] + \max{p\in[i-K+1,\,i-1]} \left(dp0[p]-pref[p]\right) ] となり、「区間内の最大値」を取る形に変形できます。

遷移（休日で終わる）

同様に、\(i\) 日目が休日で終わるなら直前に勤務で終わった日を \(p\) として、 - \(p+1,\dots,i\) が連続休日 - \(i-p \le M-1\) より \(p \ge i-M+1\) - 連続休日は1日以上なので \(p \le i-1\)

よって [ dp0[i] = \max_{p\in[i-M+1,\,i-1]} dp1[p] ]

高速化：単調キューで「スライド最大」を維持

必要なのは次の2つの“スライド区間最大”です。

1. \(dp1[i]\) 用：区間 \(p\in[i-K+1,\,i-1]\) における
   [ X[p]=dp0[p]-pref[p] ] の最大値
   → deque D1 で管理（値が大きい順に保つ）

2. \(dp0[i]\) 用：区間 \(p\in[i-M+1,\,i-1]\) における
   [ dp1[p] ] の最大値
   → deque D0 で管理（値が大きい順に保つ）

各日 \(i\) について、 - 区間外（左端より小さい index）の要素を deque の先頭から捨てる - deque 先頭がその区間の最大値 - 新しい候補（\(i\) を index とする値）を「後ろから小さいものを消して」追加

これで各 index は高々1回追加・1回削除されるため全体 \(O(N)\) になります。

最後に答えは \(N\) 日目が勤務でも休日でもよいので [ \max(dp0[N], dp1[N]) ] が最大給料です。両方が不可能なら -1 を出します。

計算量

• 時間計算量: \(O(N)\)（各 index が deque に入る／出るのが高々1回）
• 空間計算量: \(O(K+M)\) 程度（deque に保持される要素数は窓幅に比例、最悪でも \(O(N)\)）

実装のポイント

• 不可能状態を表すために十分小さい値（コードでは INF_NEG=-10**30）を使い、deque に追加する前に「到達可能か」を判定しています。

• \(dp1[i]\) の式を [ dp1[i]=pref[i]+\max(dp0[p]-pref[p]) ] に変形するのが最重要で、これにより「区間最大」問題に落とせます。

• 区間の左端は \(i-K+1\) や \(i-M+1\) が負になることがあるので、\(0\) で丸めています（コードの L1,L0）。

  ソースコード

import sys
from collections import deque

INF_NEG = -10**30

def push_max(deq, idx, val):
    while deq and deq[-1][1] <= val:
        deq.pop()
    deq.append((idx, val))

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

    # D1: for dp1[i] = pref[i] + max(dp0[p] - pref[p]) over p in [i-K+1, i-1]
    # D0: for dp0[i] = max(dp1[p]) over p in [i-M+1, i-1]
    D1 = deque()
    D0 = deque()
    push_max(D1, 0, 0)  # dp0[0] - pref[0]
    push_max(D0, 0, 0)  # dp1[0]

    pref = 0
    dp0_i = 0
    dp1_i = 0

    for i in range(1, N + 1):
        pref += A[i - 1]

        L1 = i - K + 1
        if L1 < 0:
            L1 = 0
        L0 = i - M + 1
        if L0 < 0:
            L0 = 0

        while D1 and D1[0][0] < L1:
            D1.popleft()
        while D0 and D0[0][0] < L0:
            D0.popleft()

        dp1_i = pref + (D1[0][1] if D1 else INF_NEG)
        dp0_i = (D0[0][1] if D0 else INF_NEG)

        if dp0_i > INF_NEG // 2:
            push_max(D1, i, dp0_i - pref)
        if dp1_i > INF_NEG // 2:
            push_max(D0, i, dp1_i)

    ans = max(dp0_i, dp1_i)
    if ans <= INF_NEG // 2:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

---

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