Overview

This problem asks us to maximize the total salary earned over \(N\) days of shifts, subject to the constraints that “consecutive working days must be at most \(K-1\)” and “consecutive rest days must be at most \(M-1\).”

By combining dynamic programming (DP) with an efficient sliding window maximum technique (using a deque), we can quickly find the optimal schedule among a vast number of choices.

Analysis

1. State Definition

At each day, we need to choose whether to “work” or “rest.” Due to the constraints on consecutive days, it becomes important to track “when was the last rest day” or “when was the last working day.” Therefore, we define the following two DP tables:

• \(dp\_work[i]\): The maximum total salary up to day \(i\) when we work on day \(i\)
• \(dp\_rest[i]\): The maximum total salary up to day \(i\) when we rest on day \(i\)

2. Transition Logic

• Computing \(dp\_work[i]\): To work on day \(i\), the most recent rest day must have been some day \(j\). Due to the consecutive work limit (cannot work \(K\) or more consecutive days), we need \(i - j < K\), i.e., \(j \geq i - K + 1\). When resting on day \(j\) and then working consecutively from day \(j+1\) to day \(i\), the salary can be expressed using the prefix sum \(S\) as \((S[i] - S[j])\). $\(dp\_work[i] = \max_{i-K+1 \le j \le i-1} \{ dp\_rest[j] + S[i] - S[j] \}\)\( Rearranging this, we get \)\max { dp_rest[j] - S[j] } + S[i]$, which reduces to finding the maximum value within a range.

• Computing \(dp\_rest[i]\): To rest on day \(i\), the most recent working day must have been some day \(j\). Due to the consecutive rest limit (cannot rest \(M\) or more consecutive days), we need \(j \geq i - M + 1\). $\(dp\_rest[i] = \max_{i-M+1 \le j \le i-1} \{ dp\_work[j] \}\)\( (However, if we rest from day 1 through day \)i\( without ever working, this is only valid when \)i < M\(, in which case we consider the salary as \)0$.)

3. Need for Optimization

Naively searching over all \(j\) for each \(i\) would take \(O(NK)\) or \(O(NM)\) time, which is too slow given the constraints (\(N = 2 \times 10^5\)). However, looking at the transition formulas, we are simply finding “the maximum value within a specific range,” so by using the sliding window maximum algorithm (with a double-ended queue/deque), each transition can be performed in \(O(1)\).

Algorithm

1. Prepare prefix sums: Compute the prefix sum \(S\) of the salaries \(A\) so that the total salary for any interval can be obtained in \(O(1)\).
2. Initialize deques:
   • dq_rest_S: A deque managing values of \((dp\_rest[j] - S[j])\).
   • dq_work: A deque managing values of \(dp\_work[j]\).
3. Execute DP: Repeat the following for \(i = 1\) to \(N\):
   • Check the front of each deque and remove old indices that are out of range (less than \(i-K+1\) or \(i-M+1\)).
   • Use the maximum value at the front of the deque to update \(dp\_work[i]\) and \(dp\_rest[i]\).
   • Add the newly computed values to the deques. When doing so, remove any values at the back of the deque that are smaller than the new value, since they can never become the maximum in the future.
4. Output the result: The answer is \(\max(dp\_work[N], dp\_rest[N])\).

Complexity

• Time complexity: \(O(N)\)
  • Each element is added to the deque at most once and removed at most once, so the total is \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the DP tables, prefix sums, and deques.

Implementation Notes

• Initial state: We start from the state of “resting” on day 0 (\(dp\_rest[0] = 0\)), and by placing this in the deque, we can correctly compute working from day 1 onward.

• Negative infinity: To handle unreachable states, we initialize with a very small value (such as \(-10^{18}\)). However, under this problem’s constraints (\(K, M \ge 2\)), there always exists some valid shift arrangement.

• Leveraging prefix sums: The key insight when computing dp_work[i] is that by separating out \(S[i]\), we can consolidate the value stored in the deque into a single term \(dp\_rest[j] - S[j]\).

  Source Code

import sys
import collections

# 競技プログラミングのエキスパートとして、与えられた制約と条件を効率的に処理するコードを実装します。
# 連続勤務日数 K 未満、連続休日数 M 未満という条件を動的計画法（DP）とスライディングウィンドウ最大値（デック）を用いて
# O(N) の時間計算量で解きます。

def solve():
    # 標準入力から全データを読み込み、高速に処理します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    M = int(input_data[2])
    A = list(map(int, input_data[3:]))

    # 給料の累積和を計算します。
    # S[i] は 1 日目から i 日目までの給料の合計を表します。
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + A[i]

    # dp_work[i]: i 日目にシフトに入った場合の、i 日目までの給料の最大合計
    # dp_rest[i]: i 日目に休みを入れた場合の、i 日目までの給料の最大合計
    INF = 10**18
    dp_work = [-INF] * (N + 1)
    dp_rest = [-INF] * (N + 1)

    # 0 日目は便宜上「休み」の状態からスタートすると考えます。
    dp_rest[0] = 0
    
    # スライディングウィンドウ最大値を効率的に求めるためのデックを用意します。
    # dq_rest_S は (dp_rest[j] - S[j]) を最大化するインデックス j を保持します。
    dq_rest_S = collections.deque([0])
    # dq_work は dp_work[j] を最大化するインデックス j を保持します。
    dq_work = collections.deque()

    for i in range(1, N + 1):
        # 1. i 日目に働く場合 (dp_work[i] の計算)
        # 直近の休みを j 日目 (max(0, i-K+1) <= j <= i-1) とすると、
        # j+1 日目から i 日目まで連続して働くことになります。
        # その時の給料合計は (S[i] - S[j]) + dp_rest[j] です。
        while dq_rest_S and dq_rest_S[0] < i - K + 1:
            dq_rest_S.popleft()
        
        if dq_rest_S:
            best_j = dq_rest_S[0]
            dp_work[i] = S[i] - S[best_j] + dp_rest[best_j]
        
        # 2. i 日目に休む場合 (dp_rest[i] の計算)
        # 直近の勤務を j 日目 (max(1, i-M+1) <= j <= i-1) とすると、
        # j+1 日目から i 日目まで連続して休むことになります。
        # また、1 日目から i 日目まで全て休む場合は i < M の時のみ可能です。
        while dq_work and dq_work[0] < i - M + 1:
            dq_work.popleft()
        
        res = -INF
        if i < M:
            res = 0 # 全て休む場合
        if dq_work:
            if dp_work[dq_work[0]] > res:
                res = dp_work[dq_work[0]]
        dp_rest[i] = res

        # 3. 次の日以降の計算のためにデックを更新します。
        # dq_work の更新
        if dp_work[i] > -INF:
            while dq_work and dp_work[dq_work[-1]] <= dp_work[i]:
                dq_work.pop()
            dq_work.append(i)
        
        # dq_rest_S の更新
        if dp_rest[i] > -INF:
            val = dp_rest[i] - S[i]
            while dq_rest_S and (dp_rest[dq_rest_S[-1]] - S[dq_rest_S[-1]]) <= val:
                dq_rest_S.pop()
            dq_rest_S.append(i)

    # N 日間のシフトが終わった時点で、最後の状態が「勤務」か「休み」かの最大値を取ります。
    # 条件を満たす組み方が存在しない場合は -1 を出力しますが、K, M >= 2 の制約下では常に存在します。
    ans = max(dp_work[N], dp_rest[N])
    if ans < 0:
        print("-1")
    else:
        print(ans)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.