Overview

In an \(N\)-day shift schedule, we want to maximize total salary while keeping consecutive working days to at most \(K-1\) and consecutive rest days to at most \(M-1\). We solve this in \(O(N)\) by combining DP with sliding window maximum.

Analysis

Key Observation

Each day has two choices: “work” or “rest.” The constraints are:

• You must not work \(K\) or more consecutive days (at most \(K-1\) consecutive working days)
• You must not rest \(M\) or more consecutive days (at most \(M-1\) consecutive rest days)

DP State Design

We manage the maximum salary up to day \(i\) by separating based on whether the last day is a work day or a rest day.

• \(\text{dp\_work}[i]\): Maximum salary when the shifts for days \(1\) through \(i\) are decided and day \(i\) is a work day
• \(\text{dp\_rest}[i]\): Maximum salary when the shifts for days \(1\) through \(i\) are decided and day \(i\) is a rest day

Deriving Transitions

Transition for dp_work[i]: When working on day \(i\), consider the starting point of the current consecutive work streak. Since consecutive working days are at most \(K-1\), the last rest day \(j\) must satisfy \(j \geq i - K + 1\). If day \(j\) is the last rest day, then days \(j+1\) through \(i\) are all work days, earning a salary of \(\text{prefix}[i] - \text{prefix}[j]\).

\[\text{dp\_work}[i] = \max_{j \in [\max(0,\, i-K+1),\, i-1]} \left( \text{dp\_rest}[j] + \text{prefix}[i] - \text{prefix}[j] \right)\]

Rearranging:

\[\text{dp\_work}[i] = \text{prefix}[i] + \max_{j \in [\max(0,\, i-K+1),\, i-1]} \left( \text{dp\_rest}[j] - \text{prefix}[j] \right)\]

Transition for dp_rest[i]: When resting on day \(i\), the last work day \(j\) must satisfy \(j \geq i - M + 1\). Days \(j+1\) through \(i\) are all rest days, so no salary is added.

\[\text{dp\_rest}[i] = \max_{j \in [\max(0,\, i-M+1),\, i-1]} \text{val\_for\_rest}[j]\]

Here, \(\text{val\_for\_rest}[j] = \text{dp\_work}[j]\) (for \(j \geq 1\)), and \(\text{val\_for\_rest}[0] = 0\) (the case of resting from the very beginning).

Problem with the Naive Approach

Naively computing the maximum within the window for each \(i\) results in \(O(NK)\) or \(O(NM)\), which risks TLE when \(N\) is up to \(2 \times 10^5\).

Solution: Sliding Window Maximum

Using a monotonic queue (deque), we can find the maximum within a sliding window in amortized \(O(1)\) per step.

Algorithm

1. Compute the prefix sum \(\text{prefix}[i]\).
2. Initial values: \(\text{dp\_rest}[0] = 0\) (rest state after 0 days), \(\text{dp\_work}[0] = -\infty\).
3. Prepare two monotonic queues:
   • dq_work: Sliding window maximum of \(\text{dp\_rest}[j] - \text{prefix}[j]\) (window size \(K\))
   • dq_rest: Sliding window maximum of \(\text{val\_for\_rest}[j]\) (window size \(M\))
4. For \(i = 1, 2, \ldots, N\) in order:
   • Remove elements outside the window from dq_work, then \(\text{dp\_work}[i] = \text{prefix}[i] +\) the front value of the queue
   • Remove elements outside the window from dq_rest, then \(\text{dp\_rest}[i] =\) the front value of the queue
   • Add new values to each queue (removing unnecessary elements from the back to maintain monotonicity)
5. The answer is \(\max(\text{dp\_work}[N],\, \text{dp\_rest}[N])\). If it is \(-\infty\), output -1.

Concrete Example

For \(N=5,\, K=3,\, M=2,\, A=[3, 1, 4, 1, 5]\):

• At most 2 consecutive work days, at most 1 consecutive rest day
• For example, “work, work, rest, work, work” → \(3+1+0+1+5=10\)
• “work, rest, work, work, rest” → \(3+0+4+1+0=8\)

The optimal solution is the maximum among all combinations satisfying the constraints.

Complexity

• Time complexity: \(O(N)\) (each element is added to and removed from the queue at most once)
• Space complexity: \(O(N)\) (DP arrays, prefix sums, queues)

Implementation Notes

• Handling base cases: \(j=0\) represents the state where “no day has been decided yet.” \(\text{dp\_rest}[0]=0\) (starting with all rest), \(\text{dp\_work}[0]=-\infty\) (it is impossible to work on day 0). Setting \(\text{val\_for\_rest}[0]=0\) correctly handles the case of resting from the beginning.

• Rearranging transitions: In the transition for \(\text{dp\_work}\), by grouping \(\text{dp\_rest}[j] - \text{prefix}[j]\) together, we can factor \(\text{prefix}[i]\) out of the window. This makes the monotonic queue applicable.

• Infeasibility detection: In cases like \(K=1\) (cannot work even one day) and \(M=1\) (cannot rest even one day), no solution exists when \(N \geq 1\). If the final answer remains \(-\infty\), output -1.

  Source Code

import sys
from collections import deque

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    M = int(input_data[2])
    A = [int(input_data[3 + i]) for i in range(N)]
    
    # State: dp[i][0] = max salary considering days 0..i-1, where day i-1 is a rest day
    #        dp[i][1] = max salary considering days 0..i-1, where day i-1 is a work day
    # 
    # Actually, let's think more carefully with DP.
    # 
    # Let dp[i] = maximum salary for the first i days, where the i-th day's status is determined.
    # We need to track consecutive work/rest days which makes this complex.
    #
    # Alternative approach:
    # dp_work[i] = max total salary for days 1..i where day i is a work day
    # dp_rest[i] = max total salary for days 1..i where day i is a rest day
    #
    # For dp_work[i]: day i is worked. Before day i, there could be 0..K-2 consecutive work days.
    #   So the last rest day before this work streak was at some day j where i - j <= K-1, i.e., j >= i-K+1
    #   dp_work[i] = max over j in [max(0, i-K+1)..i-1] of dp_rest[j] + sum(A[j+1..i])
    #   Also j=0 means all days 1..i are worked (if i <= K-1).
    #
    # For dp_rest[i]: day i is rest. Before day i, there could be 0..M-2 consecutive rest days.
    #   So the last work day before this rest streak was at some day j where i - j <= M-1, i.e., j >= i-M+1
    #   dp_rest[i] = max over j in [max(0, i-M+1)..i-1] of dp_work[j]
    #   Also j=0 means all days 1..i are rest (if i <= M-1).
    
    # prefix sum for A (1-indexed: prefix[i] = A[0]+...+A[i-1])
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    NEG_INF = float('-inf')
    
    # dp_work[i]: max salary for days 1..i, day i is work. i from 1..N
    # dp_rest[i]: max salary for days 1..i, day i is rest. i from 1..N
    # We also define dp_work[0] = NEG_INF (no day 0 to work), dp_rest[0] = 0 (base: no days, trivially rest)
    
    dp_work = [NEG_INF] * (N + 1)
    dp_rest = [NEG_INF] * (N + 1)
    dp_rest[0] = 0
    
    # dp_work[i] = max over j in [max(0, i-K+1)..i-1] of (dp_rest[j] - prefix[j]) + prefix[i]
    # So we need max of (dp_rest[j] - prefix[j]) over sliding window of size K for j.
    
    # dp_rest[i] = max over j in [max(0, i-M+1)..i-1] of dp_work[j]
    # But also j=0 is allowed if i <= M-1: dp_rest[0] = 0.
    # Sliding window of size M for dp_work[j], but also including j=0 via dp_rest[0].
    # Actually dp_rest[i] = max over j in [max(0,i-M+1)..i-1] of dp_work[j], plus j=0 gives 0 if 0 >= i-M+1.
    # We handle j=0 separately since dp_work[0] = NEG_INF. Let's instead:
    # For dp_rest: we want max of dp_work[j] for j in [max(0,i-M+1)..i-1], but also if i <= M-1, we can have all rest -> 0.
    # Let's define val_rest[j] = dp_work[j] for j>=1, val_rest[0] = 0. Then dp_rest[i] = max of val_rest[j] for j in window.
    
    val_for_work = [NEG_INF] * (N + 1)  # dp_rest[j] - prefix[j]
    val_for_work[0] = dp_rest[0] - prefix[0]  # = 0
    
    val_for_rest = [NEG_INF] * (N + 1)  # dp_work[j] for j>=1, 0 for j=0
    val_for_rest[0] = 0
    
    # Sliding window max using deque
    dq_work = deque()  # for computing dp_work, window over val_for_work
    dq_work.append(0)
    
    dq_rest = deque()  # for computing dp_rest, window over val_for_rest
    dq_rest.append(0)
    
    for i in range(1, N + 1):
        # dp_work[i]: window [max(0, i-K+1)..i-1] over val_for_work
        while dq_work and dq_work[0] < i - K + 1:
            dq_work.popleft()
        if dq_work:
            dp_work[i] = val_for_work[dq_work[0]] + prefix[i]
        
        # dp_rest[i]: window [max(0, i-M+1)..i-1] over val_for_rest
        while dq_rest and dq_rest[0] < i - M + 1:
            dq_rest.popleft()
        if dq_rest:
            dp_rest[i] = val_for_rest[dq_rest[0]]
        
        # Update val_for_work[i] and add to dq_work
        val_for_work[i] = dp_rest[i] - prefix[i]
        while dq_work and val_for_work[dq_work[-1]] <= val_for_work[i]:
            dq_work.pop()
        dq_work.append(i)
        
        # Update val_for_rest[i] and add to dq_rest
        val_for_rest[i] = dp_work[i]
        while dq_rest and val_for_rest[dq_rest[-1]] <= val_for_rest[i]:
            dq_rest.pop()
        dq_rest.append(i)
    
    ans = max(dp_work[N], dp_rest[N])
    
    # Also need to consider ending with rest: last work day j, then rest days j+1..N, need N-j <= M-1
    # This is already handled by dp_rest[N].
    
    if ans == NEG_INF:
        print(-1)
    else:
        print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.