Overview

In this problem, given a period of \(N\) days with a constraint that once you work a part-time job, you cannot work for the next \(D\) days, we need to find the maximum total salary that can be earned by working at most \(K\) days.

Analysis

The Case \(D = 0\)

When no rest period is required (\(D = 0\)), there are no constraints on the interval between working days. Therefore, it is optimal to choose the top \(\min(N, K)\) days with the largest salaries \(A_i\). This can be solved in \(O(N \log N)\) by sorting the array.

The Case \(D \ge 1\)

If you work on a certain day, you cannot work for the immediately following \(D\) days. Thus, the choice of which days can be selected later depends on which day was chosen previously. Since past choices affect future options and there are overlapping subproblems for future optimization, it is natural to use Dynamic Programming (DP).

Naively searching over all combinations of days worked would result in an exponential number of states, leading to Time Limit Exceeded (TLE).

DP State and Transition Design

Let \(i\) be the index representing the day, and \(j\) be the index representing the number of days worked. A straightforward state definition is: - \(DP[j][i] = \) “the maximum total salary earned by working a total of \(j\) days up to day \(i\)”

There are two possible choices for day \(i\): 1. Do not work on day \(i\): The maximum value up to day \(i-1\) is carried over directly (\(DP[j][i-1]\)). 2. Work on day \(i\): The previous work day must be on or before day \(i - (D + 1)\). Therefore, the value is the maximum value earned by working \(j-1\) days up to day \(\max(0, i - (D + 1))\) plus \(A_i\) (\(DP[j-1][\max(0, i - D - 1)] + A_i\)).

By taking the maximum of these two options, each state transition can be computed in \(O(1)\).

Reducing the Upper Bound of \(K\)

The maximum number of days that can be chosen within \(N\) days with an interval of at least \(D\) days between them is: \(1 + \left\lfloor \frac{N - 1}{D + 1} \right\rfloor\) days. If the given \(K\) in the input is larger than this, it is physically impossible to work \(K\) days. By clamping \(K\) to this maximum value in advance, we can eliminate unnecessary computations (when \(D \ge 1\), the clamped \(K\) is at most approximately \(N / 2\)).

Algorithm

1. Handling the Corner Case: If \(D = 0\), sort the array \(A\) in descending order, output the sum of the first \(K\) elements, and terminate.
2. Clamp the Upper Bound of \(K\): Update \(K \leftarrow \min\left(K, 1 + \left\lfloor \frac{N - 1}{D + 1} \right\rfloor\right)\).
3. Updating the DP Table:
   • To update \(DP[j][i]\), only the results from row \(j-1\) are required. Therefore, we can maintain and alternate between two rows of arrays (the previous row prev_f and the current row curr_f) (rolling array).
   • Loop \(j\) from \(1\) to \(K\).
   • In order to work for the \(j\)-th time, the day must be at least \((j - 1)(D + 1) + 1\). Thus, start the inner loop \(i\) from this value.
   • For each \(i\), compute curr_f[i] according to the transition formula: $\(p = \max(0, i - (D + 1))\)\( \)\(\text{curr\_f}[i] = \max(\text{curr\_f}[i - 1], \text{prev\_f}[p] + A_i)\)$
   • For each \(j\), update the overall answer with \(\text{curr\_f}[N]\), the maximum value up to the final day.

Complexity

• Time Complexity: \(O(N \cdot K)\)
  • When \(D = 0\), it is \(O(N \log N)\) for sorting.
  • When \(D \ge 1\), the clamped \(K\) is at most approximately \(N/2\). Since the outer loop runs \(K\) times and the inner loop runs at most \(N\) times, the overall time complexity is \(O(N \cdot K) \le O(N^2 / 2)\). When \(N = 5000\), the number of loop iterations is at most around \(1.25 \times 10^7\), which is well within the time limit.
• Space Complexity: \(O(N)\)
  • Since we only keep two 1D arrays of length \(N + 1\), the space complexity is \(O(N)\), which is very memory-efficient.

Key Implementation Points

• Embedding the prefix maximum into the DP state: By defining \(DP[j][i]\) as “the maximum value earned by working \(j\) days up to day \(i\)” rather than “the maximum value earned when working the \(j\)-th day exactly on day \(i\)”, we can reference the previous optimal value in \(O(1)\).

• Initialization of impossible states: To prevent transitions from states that do not satisfy the working conditions, initialize the DP table with a sufficiently small value (\(-\infty\), such as \(-10^{18}\)).

  Source Code

import sys


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    K = int(input_data[1])
    D = int(input_data[2])
    A = [int(x) for x in input_data[3 : 3 + N]]

    if D == 0:
        A.sort(reverse=True)
        print(sum(A[:K]))
        return

    max_k = 1 + (N - 1) // (D + 1)
    K = min(K, max_k)

    INF = 10**18
    prev_f = [0] * (N + 1)
    ans = 0
    step = D + 1

    for j in range(1, K + 1):
        curr_f = [-INF] * (N + 1)
        start_i = (j - 1) * step + 1
        for i in range(start_i, N + 1):
            p = i - step if i > step else 0
            val = prev_f[p] + A[i - 1]
            c = curr_f[i - 1]
            curr_f[i] = val if val > c else c

        if curr_f[N] > ans:
            ans = curr_f[N]
        prev_f = curr_f

    print(ans)


if __name__ == "__main__":
    main()

---

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