Overview

In this problem, we want to choose at most \(K\) days to work out of \(N\) days to maximize the total salary earned, subject to the interval constraint: “you cannot work for the \(D\) days immediately following any day you work.” This can be solved using dynamic programming (DP) with two dimensions: the number of days considered and the number of days worked.

Analysis

Naive Approach

The first idea that comes to mind is to try all possible subsets of days to work. However, there are \(2^N\) subsets, which is far too slow for \(N \le 5000\).

Next, one might consider a greedy approach: “repeatedly pick days with the highest salary.” However, this is incorrect. For example, when \(N=3, K=2, D=1\), and \(A = (5, 6, 5)\): - If we greedily pick \(A_2 = 6\) first, working on day \(2\) forbids working on day \(3\), and working on day \(1\) would have forbidden working on day \(2\). Thus, picking day \(2\) prevents us from picking any other day, resulting in a total of \(6\). - On the other hand, if we choose days \(1\) and \(3\), we get \(5 + 5 = 10\), which is optimal.

In this way, making the choice to “take the larger value” eliminates future options, so a greedy approach does not work.

Key Observation

The key is that the constraint “if you work on day \(i\), the next day you can work is day \(i + D + 1\) or later” depends only on the most recent day worked. In other words, if we track:

• How many days we have considered so far
• How many days we have worked so far

as the state, the specific details of earlier choices do not affect the outcome (for the same state, we only need to keep the choice that yields the maximum salary). This is a classic setup for DP.

Algorithm

Let \(dp[j][i]\) be defined as “the maximum total salary earned considering only the first \(i\) days, having worked at most \(j\) days” (the key point is to define it as “at most \(j\) days” rather than “exactly \(j\) days,” which allows the final answer to simply be \(dp[K][N]\)).

The transitions are divided into two cases depending on whether we work on day \(i\):

1. Do not work on day \(i\): We can simply take \(dp[j][i-1]\).
2. Work on day \(i\): The previous day worked must be on or before day \(i - D - 1\). Therefore, we have: $\(dp[j-1][\max(0,\; i-D-1)] + A_i\)$

Putting it together: $\(dp[j][i] = \max\bigl(dp[j][i-1],\; dp[j-1][\max(0,\,i-D-1)] + A_i\bigr)\)$

The base cases are \(dp[0][i] = 0\) (working \(0\) days yields \(0\) salary) and \(dp[j][0] = 0\).

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

Tracing this with the concrete example (\(N=3, K=2, D=1\), \(A=(5,6,5)\)): - \(dp[1][1]=5,\ dp[1][2]=6,\ dp[1][3]=6\) - \(dp[2][1]=5\), \(dp[2][2]=\max(dp[2][1], dp[1][0]+6)=6\), \(dp[2][3]=\max(dp[2][2], dp[1][1]+5)=\max(6, 10)=10\)

which correctly gives \(10\).

Complexity

• Time Complexity: \(O(NK)\) (Since \(N, K \le 5000\), this requires at most about \(2.5 \times 10^7\) simple operations, which is sufficiently fast)
• Space Complexity: \(O(N)\) (Since we only need the previous row for \(j\), we can alternate between two arrays. A straightforward 2D array would take \(O(NK)\), which is \(5000 \times 5000 \times 8\) bytes \(= 200\) MB and could risk exceeding memory limits, so rolling arrays is safer)

Implementation Details

• Index Out of Bounds: When \(i - D - 1\) is negative, clamp it to \(0\) (idx = max(i-D-1, 0)). Since \(dp[\cdot][0] = 0\), this naturally handles the case where there is no previously worked day.

• Case where \(D = 0\): In this case, the reference becomes \(dp[j-1][i-1]\), correctly representing that consecutive days can be worked. No special case handling is needed.

• Overflow: Since \(A_i \le 10^9\) and there are up to \(5000\) days, the sum can reach up to \(5 \times 10^{12}\). Use long long (a 64-bit integer).

• Reusing Arrays: Maintain prev (for row \(j-1\)) and cur (for row \(j\)), and swap them at the end of the \(j\) loop. Make sure not to forget initializing cur[0] = 0 in each iteration.

• Because of the “at most \(K\) days” definition, the transition automatically yields the correct answer even if the interval constraint prevents working all \(K\) days (since the transition from dp[j][i-1] allows leaving some allowed work days unused).

  Source Code

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,K,D;
    if(scanf("%d %d %d",&N,&K,&D)!=3) return 0;
    vector<long long> A(N+1);
    for(int i=1;i<=N;i++) scanf("%lld",&A[i]);
    vector<long long> prev(N+1,0), cur(N+1,0);
    // prev = dp[0][*] = 0
    for(int j=1;j<=K;j++){
        cur[0]=0;
        for(int i=1;i<=N;i++){
            int idx = i-D-1; if(idx<0) idx=0;
            long long v = prev[idx]+A[i];
            long long w = cur[i-1];
            cur[i] = v>w?v:w;
        }
        swap(prev,cur);
    }
    printf("%lld\n", prev[N]);
    return 0;
}

---

This editorial was generated by claude5opus-high.