Overview

This problem asks us to maximize the total salary earned by choosing at most \(K\) days out of \(N\) days, subject to the constraint that any two chosen days must be separated by at least \(D+1\) days (meaning at least \(D\) rest days between them). We can solve this efficiently using dynamic programming (DP) and maintaining a running maximum (two-pointer approach).

Analysis

1. Problem Restatement

If day \(p\) is a working day and day \(q\) is the next working day, the problem conditions require the following: - \(q \ge p + D + 1\) (because after working on day \(p\), a rest period of \(D\) days is required) - The total number of chosen days must be between \(1\) and \(K\) inclusive (since \(A_i \ge 1\), it is always optimal to work at least \(1\) day if possible)

2. Naive Approach and Its Limitations

Consider a dynamic programming approach where the state is “the maximum salary when working for \(j\) days in total, with the last working day being day \(i\).” Denoting this state as \(\text{dp}[j][i]\), the transition from the previous working day \(p\) is as follows:

\[ \text{dp}[j][i] = \max_{1 \le p \le i - D - 1} (\text{dp}[j-1][p]) + A_i \]

If we compute this transition naively: - Number of days worked \(j\): \(1 \le j \le K\) (\(O(K)\) states) - Last working day \(i\): \(1 \le i \le N\) (\(O(N)\) states) - Previous working day \(p\): \(1 \le p \le i - D - 1\) (\(O(N)\) candidates)

In total, this takes \(O(K \times N^2)\) time. Since \(N, K \le 5000\), the number of operations can be up to \(5000^3 \approx 1.25 \times 10^{11}\), which exceeds the time limit and results in TLE (Time Limit Exceeded).

3. Optimization

As \(i\) increases from \(1\) to \(N\), the upper bound of the valid range of transitions \(p\), which is \(i - D - 1\), also increases monotonically. Therefore, we do not need to iterate over \(p\) from \(1\) each time to find the maximum. Instead, by maintaining the maximum value of \(\text{dp}[j-1][p]\) seen so far while advancing a pointer, we can retrieve the maximum value for each \(i\) in \(O(1)\) time.

This allows us to perform the computation for each \(j\) in \(O(N)\) time, reducing the overall time complexity to \(O(NK)\).

Algorithm

1. Initialization:
   • For \(j = 1\) (working for only 1 day), the salary earned by working on day \(i\) is \(A_i\).
   • Set prev_dp[i] = A[i], and initialize the maximum answer ans with these values as well.
2. Updating the DP Table:
   • Loop through the number of working days \(j\) from \(2\) to \(K\).
   • Initialize a variable max_val = -1 to hold the maximum value up to the current point, and a pointer ptr = 1 to track the valid transition days.
   • While advancing the current day \(i\) from \(1\) to \(N\), perform the following:
     1. While ptr <= i - D - 1, update max_val = max(max_val, prev_dp[ptr]) and increment ptr.
     2. If max_val != -1 (a valid transition source exists), set curr_dp[i] = max_val + A[i].
     3. Update the answer with ans = max(ans, curr_dp[i]).
   • If no updates occurred for any \(i\) (meaning it is impossible to work any more days under the constraints), break out of the loop early since checking further values of \(j\) is unnecessary.
   • Replace prev_dp with curr_dp and proceed to the next \(j\).
3. Output:
   • Print the final value of ans.

Complexity

• Time Complexity: \(O(N \cdot K)\)
  • The outer loop runs at most \(K\) times.
  • In the inner loop, as \(i\) ranges from \(1\) to \(N\), the pointer ptr also advances to at most \(N\). Therefore, each iteration of the outer loop takes \(O(N)\) time.
  • Thus, the overall time complexity is \(O(N \cdot K) \le 5000 \times 5000 = 2.5 \times 10^7\), which easily runs well within the standard time limit (usually 2 seconds).
• Space Complexity: \(O(N)\)
  • By using a “rolling array” technique to store only the states for day \(j-1\) (prev_dp) and day \(j\) (curr_dp), the memory requirement is kept to \(O(N)\).

Implementation Notes

• Preventing Overflow: The maximum total salary can reach \(5000 \times 10^9 = 5 \times 10^{12}\), which exceeds the range of a 32-bit integer (int). Make sure to use a 64-bit integer type (long long in C++) for the DP table and the answer variable.

• Handling Unreachable States: Represent states where it is impossible to work on that day for that number of days with a sentinel value such as -1, ensuring that invalid transitions (transitions from unreachable states) do not occur.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, d;
    if (!(cin >> n >> k >> d)) return 0;

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

    vector<long long> prev_dp(n + 1, -1);
    long long ans = 0;

    for (int i = 1; i <= n; ++i) {
        prev_dp[i] = a[i];
        ans = max(ans, prev_dp[i]);
    }

    vector<long long> curr_dp(n + 1, -1);

    for (int j = 2; j <= k; ++j) {
        long long max_val = -1;
        int ptr = 1;
        bool any_valid = false;

        for (int i = 1; i <= n; ++i) {
            curr_dp[i] = -1;
            while (ptr <= i - d - 1) {
                if (prev_dp[ptr] != -1) {
                    max_val = max(max_val, prev_dp[ptr]);
                }
                ptr++;
            }
            if (max_val != -1) {
                curr_dp[i] = max_val + a[i];
                ans = max(ans, curr_dp[i]);
                any_valid = true;
            }
        }

        if (!any_valid) {
            break;
        }

        prev_dp = curr_dp;
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.8-flash-high.