Overview

We want to maximize the total salary earned by working at most \(K\) days, such that the gap between any two chosen workdays is at least \(D+1\) days. We solve this using dynamic programming, where the state tracks “up to which day we have considered” and “at most how many days we can work.”

Analysis

Greedily Choosing Days with Highest Pay Does Not Work

If you work on a certain day, you cannot work for the next \(D\) days. Therefore, choosing a high-paying day might prevent you from choosing other, more favorable days.

For example, consider the case where \(N=3,\ K=2,\ D=1\), and the salaries are \((6,10,6)\).

• If we pick Day \(2\), which has the maximum salary, we cannot pick Day \(1\) or Day \(3\), resulting in a total of \(10\).
• If we pick Day \(1\) and Day \(3\), the total is \(12\).

Therefore, a greedy approach of selecting days in descending order of salary does not work. Furthermore, checking all combinations of working days would take up to \(2^N\) possibilities, which is too slow to pass within the time limit.

Branching on Whether to Work on the Last Day

When considering a schedule from Day \(1\) to Day \(i\), there are two possibilities:

• Do not work on Day \(i\): We directly use the optimal schedule up to Day \(i-1\).
• Work on Day \(i\): Since the last previous day we could work is Day \(i-D-1\), we take the optimal schedule within that range and add \(A_i\).

In this way, we can use dynamic programming by building upon the solutions for shorter intervals.

Upper Bound on the Number of Days Actually Worked

To work for \(m\) days, there must be at least \(D\) rest days between any two workdays. Therefore,

\(m+(m-1)D \le N\)

must hold, meaning the maximum number of days one can work is at most

\(\left\lfloor \dfrac{N+D}{D+1} \right\rfloor\).

This can be achieved by working on days \(1,\ 1+(D+1),\ 1+2(D+1),\dots\).

Thus, it suffices to consider up to

\(K'=\min\left(K,\left\lfloor \dfrac{N+D}{D+1} \right\rfloor\right)\)

days. In the code, K is updated to this value.

Algorithm

1. Defining the DP State

Let \(dp[k][i]\) be:

The maximum total salary obtained by working at most \(k\) days between Day \(1\) and Day \(i\).

The base cases are as follows:

• \(dp[0][i]=0\): If we cannot work even once, the salary is \(0\).
• \(dp[k][0]=0\): If there are no available days, the salary is \(0\).

2. Deriving the Transitions

For \(k \ge 1,\ i \ge 1\), we branch based on whether we work on Day \(i\).

When not working on Day \(i\)

The maximum achievable value is \(dp[k][i-1]\).

When working on Day \(i\)

The latest day we could have worked previously is Day \(i-D-1\), and the remaining number of days we can work is at most \(k-1\).

Setting

\(j=\max(0,i-D-1)\),

the maximum achievable value is \(dp[k-1][j]+A_i\).

Therefore, the transition formula is:

\(dp[k][i]=\max\left(dp[k][i-1],\ dp[k-1][\max(0,i-D-1)]+A_i\right)\)

Every valid schedule falls into either “do not work on Day \(i\)” or “work on Day \(i\).” Furthermore, in the latter case, restricting the previous workday to Day \(i-D-1\) or earlier guarantees that the rest condition is satisfied. Thus, this transition correctly computes the optimal value.

3. Memory Optimization Using Two Arrays

To compute \(dp[k][i]\), we only need the following values:

• The immediately preceding value with the same \(k\): \(dp[k][i-1]\)
• A value from the previous \(k\): \(dp[k-1][j]\)

Therefore, instead of storing the entire DP table, we can use two arrays of length \(N+1\):

• prev[i]: \(dp[k-1][i]\)
• cur[i]: \(dp[k][i]\)

The concrete procedure is as follows:

1. Initialize all elements of prev to \(0\).
2. For \(k=1,2,\dots,K'\) in order, perform the following:
   • Set cur[0] = 0.
   • For \(i=1,2,\dots,N\) in order, compute cur[i] using the transition formula.
   • Swap prev and cur.
3. Finally, output prev[N].

Complexity

Let \(K'=\min\left(K,\left\lfloor \dfrac{N+D}{D+1} \right\rfloor\right)\). Then:

• Time Complexity: \(O(NK')\) (worst case \(O(NK)\))
• Space Complexity: \(O(N)\)

Each DP state can be computed in constant time. Even in the worst case, the number of states is around \(5000 \times 5000\).

Key Implementation Points

• Use long long for the total salary
  The answer can be as large as \(5000 \times 10^9=5\times 10^{12}\), which overflows a 32-bit integer.

• The reference index is i - D - 1
  For example, when \(D=1\), working on Day \(i\) means the latest day you could have previously worked is Day \(i-2\). Be careful not to use i - D.

• Clamp the index to \(0\) if it falls before Day \(1\)
  By using max(0, i - D - 1), the case where there is no previous day available can be handled as \(dp[k-1][0]=0\).

• Define the state as “at most \(k\) days” rather than “exactly \(k\) days”
  With this definition, the initial values can simply be \(0\). It also naturally handles short prefixes where working \(k\) days is not actually possible.

• Compute days in ascending order
  cur[i] depends on the updated cur[i-1]. Even though old values remain after swapping the arrays, setting cur[0] and overwriting the rest sequentially avoids any issues.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, D;
    cin >> N >> K >> D;

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    K = min(K, (N + D) / (D + 1));

    vector<long long> prev(N + 1, 0), cur(N + 1, 0);

    for (int k = 1; k <= K; ++k) {
        cur[0] = 0;
        for (int i = 1; i <= N; ++i) {
            int j = max(0, i - D - 1);
            cur[i] = max(cur[i - 1], prev[j] + A[i]);
        }
        prev.swap(cur);
    }

    cout << prev[N] << '\n';
    return 0;
}

---

This editorial was generated by gpt-6-astra-medium.