Overview

We construct a length-\(N\) sequence where each day is either “work (1)” or “rest (0)”, under the constraints that consecutive working days are at most \(K-1\) and consecutive rest days are at most \(M-1\), and we maximize the total salary earned on working days.

Analysis

Key Observation

The constraints only determine the maximum length of consecutive identical states (work/rest), so the optimal solution can be computed by transitions that only look at the “most recent switching position”: - “From the last rest day” to “working consecutively until today” - “From the last working day” to “resting consecutively until today”

Why a Naive DP Doesn’t Work

For example, if we define: - \(dp[i][x][c]\) = maximum value when looking at the first \(i\) days, where state \(x\in\{0,1\}\) has continued for \(c\) consecutive days

then the number of states becomes \(O(N(K+M))\), which is far too slow for \(N\le 2\times 10^5\).

How to Solve It

Instead of explicitly tracking the “consecutive length”, we only maintain: - \(dp1[i]\): maximum value when the last day is a working day - \(dp0[i]\): maximum value when the last day is a rest day

and enumerate the “most recent switching day \(p\)” in the transitions.

However, as-is: - \(dp1[i]\) requires the maximum over \(p\in[i-K+1,\,i-1]\) - \(dp0[i]\) requires the maximum over \(p\in[i-M+1,\,i-1]\)

which results in \(O(NK)\) or \(O(NM)\) complexity.

Therefore, we manage the “sliding window maximum” using a monotonic deque, processing each \(i\) in amortized \(O(1)\).

Algorithm

DP Definition

When the first \(i\) days (\(1\sim i\)) have been decided: - \(dp1[i]\): maximum salary when day \(i\) ends with work - \(dp0[i]\): maximum salary when day \(i\) ends with rest

As an initial state, we prepare “day 0”: - \(dp0[0]=0,\ dp1[0]=0\)

(This naturally handles both starting with work and starting with rest.)

Impossible states are set to \(-\infty\) (in the code, INF_NEG).

Transition (Ending with Work)

If day \(i\) ends with work, let \(p\) be the last day that ended with rest: - Days \(p+1, p+2, \dots, i\) are consecutive working days - The consecutive working days constraint \(i-p \le K-1\) gives \(p \ge i-K+1\) - At least 1 consecutive working day, so \(p \le i-1\)

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

Using the prefix sum \(pref[i]=\sum_{t=1}^{i}A_t\): [ \sum_{t=p+1}^{i} A_t = pref[i]-pref[p] ]

So: [ dp1[i] = pref[i] + \max_{p\in[i-K+1,\,i-1]} \left(dp0[p]-pref[p]\right) ]

This transforms the problem into finding the “maximum value in an interval”.

Transition (Ending with Rest)

Similarly, if day \(i\) ends with rest, let \(p\) be the last day that ended with work: - Days \(p+1,\dots,i\) are consecutive rest days - The constraint \(i-p \le M-1\) gives \(p \ge i-M+1\) - At least 1 consecutive rest day, so \(p \le i-1\)

Therefore: [ dp0[i] = \max_{p\in[i-M+1,\,i-1]} dp1[p] ]

Speedup: Maintaining “Sliding Maximum” with a Monotonic Deque

We need the following two “sliding window maximums”:

1. For \(dp1[i]\): the maximum of [ X[p]=dp0[p]-pref[p] ] over the interval \(p\in[i-K+1,\,i-1]\) → Managed by deque D1 (maintaining values in decreasing order)

2. For \(dp0[i]\): the maximum of [ dp1[p] ] over the interval \(p\in[i-M+1,\,i-1]\) → Managed by deque D0 (maintaining values in decreasing order)

For each day \(i\): - Remove elements from the front of the deque that are outside the interval (index smaller than the left endpoint) - The front of the deque is the maximum value for that interval - Add the new candidate (value at index \(i\)) by removing smaller elements from the back

Since each index is added and removed from the deque at most once, the total complexity is \(O(N)\).

Finally, the answer allows day \(N\) to be either work or rest, so: [ \max(dp0[N], dp1[N]) ]

is the maximum salary. If both are impossible, output -1.

Complexity

• Time complexity: \(O(N)\) (each index enters/exits the deque at most once)
• Space complexity: About \(O(K+M)\) (the number of elements held in the deque is proportional to the window width, at most \(O(N)\))

Implementation Notes

• To represent impossible states, a sufficiently small value is used (INF_NEG=-10**30 in the code), and before adding to the deque, we check whether the state is reachable.

• The most crucial transformation is rewriting the formula for \(dp1[i]\) as: [ dp1[i]=pref[i]+\max(dp0[p]-pref[p]) ] which reduces it to a “range maximum” problem.

• The left endpoint of the interval, \(i-K+1\) or \(i-M+1\), can become negative, so it is clamped to \(0\) (L1, L0 in the code).

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.