Overview

This problem asks us to maximize the total salary over \(N\) days under the constraints of working “at most \(K\) days in total” and “if you work on a day, you cannot work for the next \(D\) days.” We solve this using Dynamic Programming (DP) with states representing ‘the number of days worked’ and ‘up to which day has been considered’.

Analysis

Naive Approach

Trying all subsets of days to work results in \(2^N\) possibilities, which cannot possibly run in time for \(N \le 5000\).

Greedy Approach Fails

A greedy approach such as “picking days in descending order of salary as long as conditions are satisfied” is incorrect. Counterexample:

• \(N=3,\ K=2,\ D=1,\ A=(3,4,3)\)
• Greedy: First, pick the maximum \(A_2=4\). Then day \(3\) is banned, and day \(1\) cannot be picked simultaneously either (since working on day \(1\) would ban day \(2\)). The total is \(4\).
• Optimal: Picking day \(1\) and day \(3\) yields \(3+3=6\).

Because “picking a large value eliminates surrounding days,” local decisions are insufficient. \(\rightarrow\) DP is necessary.

DP Design

Since the constraint states that “working on day \(i\) bans days \(i+1,\dots,i+D\),” the earliest day you can work next is day \(i+D+1\). In other words, knowing the “last day worked” makes all previous information unnecessary. Furthermore, because there is a limit of “at most \(K\) days in total,” we also need to include the number of days worked in the state.

Therefore, we define:

\[dp[j][i] = (\text{maximum total salary when working at most } j \text{ days from the first } i \text{ days})\]

Considering the two cases for day \(i\) (“do not work” vs. “work”):

\[dp[j][i] = \max\bigl(\underbrace{dp[j][i-1]}_{\text{do not work on day } i},\ \underbrace{dp[j-1][\max(0,\ i-D-1)] + A_i}_{\text{work on day } i}\bigr)\]

If you work on day \(i\), the latest day you could have previously worked is day \(i-D-1\), so we reference \(dp[j-1][i-D-1]\) (or \(dp[j-1][0]=0\) if \(i-D-1<0\)).

The answer is \(dp[K][N]\).

Additionally, since \(A_i \ge 1\) (all positive), “increasing the number of working days never hurts” (\(dp[j][i] \ge dp[j-1][i]\) holds), and \(dp[j][i]\) naturally becomes monotonic with respect to “at most \(j\) days.” Therefore, there is no need to include \(dp[j-1][i]\) directly in the transitions.

Concrete Example

For \(N=5,\ K=2,\ D=1,\ A=(1,5,3,4,2)\):

• \(j=1\): \(dp[1][i]\) is the prefix maximum of \(A_1..A_i \rightarrow 1,5,5,5,5\)
• \(j=2\):
  • \(i=1\): \(dp[1][0]+1=1 \Rightarrow 1\)
  • \(i=2\): \(dp[1][0]+5=5 \Rightarrow 5\)
  • \(i=3\): \(dp[1][1]+3=4\); since \(dp[2][2]=5\) is larger \(\Rightarrow 5\)
  • \(i=4\): \(dp[1][2]+4=9 \Rightarrow 9\)
  • \(i=5\): \(dp[1][3]+2=7\); since \(dp[2][4]=9\) is larger \(\Rightarrow 9\)

The answer is \(9\) (days \(2\) and \(4\)).

Algorithm

1. Find the upper bound on the number of days you can actually work. Working at the shortest intervals on days \(1, 1+(D+1), 1+2(D+1), \dots\) yields the maximum number of days, which is \(\left\lfloor \frac{N+D}{D+1} \right\rfloor\) days. Thus, we can set \(K \leftarrow \min\left(K, \left\lfloor \frac{N+D}{D+1} \right\rfloor\right)\) (this drastically reduces the loop iterations when \(D\) is large).
2. Compute the recurrence above with \(j\) in the outer loop and \(i\) in the inner loop. Since computing \(dp[j][\cdot]\) only depends on \(dp[j-1][\cdot]\), two arrays (prev and cur) are sufficient.
3. In the inner loop, by maintaining the “running maximum so far” in best, we can compute the \(\max\) with \(dp[j][i-1]\) in \(O(1)\) time (prefix max).
4. If \(dp[j][\cdot]\) becomes completely identical to \(dp[j-1][\cdot]\), it will not change in subsequent iterations, so we can terminate early (a state where no more working days can be added).

Complexity

• Time Complexity: \(O(N \cdot \min\left(K, \frac{N+D}{D+1}\right))\), which is \(O(N^2)\) in the worst case (when \(D=0\)). Since \(N \le 5000\), this takes around \(2.5 \times 10^7\) operations.
• Space Complexity: \(O(N)\) (maintaining only two rows of the DP array).

Implementation Notes

• Indices: Using 0-indexing for \(A\) and 1-indexing for DP representing “up to day \(i\)” reduces confusion (using A[i-1] in the code). Make sure to clamp to \(0\) when \(i-D-1 < 0\).

• Capping \(K\): When \(D\) is large (e.g., \(D=N\)), you can work at most 1 day. Bounding \(K\) by \(\left\lfloor\frac{N+D}{D+1}\right\rfloor\) significantly reduces the number of loop iterations and speeds up execution.

• Prefix Max Technique: By simply updating best = max(best, prev[max(0, i-d-1)] + A[i-1]) and setting cur[i] = best, the transition for the case where you “do not work on day \(i\)” is handled simultaneously.

• Early Termination Check: Breaking out of the loop when cur == prev eliminates unnecessary iterations (this is effective in Python because list equality checks are implemented in C and very fast).

• Overflow: The total sum can reach up to \(5000 \times 10^9 = 5 \times 10^{12}\), which exceeds 32 bits. While this is not an issue in Python, make sure to use long long in languages like C++.

• Fast Input: Since \(N\) can be large, reading the entire input at once using sys.stdin.buffer.read() is safe and efficient.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1]); d = int(data[2])
    A = list(map(int, data[3:3+n]))
    # 実際に働ける最大日数の上限
    k = min(k, (n + d) // (d + 1))
    if k <= 0:
        print(0)
        return
    prev = [0] * (n + 1)
    for _ in range(k):
        cur = [0] * (n + 1)
        best = 0
        for i in range(1, n + 1):
            p = i - d - 1
            if p < 0:
                p = 0
            v = prev[p] + A[i - 1]
            if v > best:
                best = v
            cur[i] = best
        if cur[n] == prev[n] and cur == prev:
            prev = cur
            break
        prev = cur
    print(prev[n])

main()

---

This editorial was generated by claude5opus-high.