Overview

This is a problem where you select jobs from multiple available ones while satisfying certain conditions, maximizing the total reward obtained. We sort jobs in order of earliest deadline and solve it using dynamic programming (DP) with “number of completed jobs” and “elapsed days” as states.

Analysis

At first glance, it seems like we need to consider both the selection and ordering of jobs, but there is an important principle in scheduling problems: “Jobs with deadlines should be done in order of earliest deadline first.” Intuitively, there is no benefit to postponing a job with an approaching deadline. By sorting job candidates in order of earliest deadline, we eliminate the need to worry about the “order” in which to do jobs, and only need to consider “whether to select each job or not.”

Once the order is fixed, this can be solved with dynamic programming (DP) similar to the “knapsack problem.” However, in this problem there is a special rule: “if you complete \(K\) or more jobs, you receive a bonus \(B\).” Therefore, the DP state needs to track not only “the current elapsed days” but also “the number of jobs completed so far.”

Since the bonus is the same regardless of how many jobs are completed as long as it’s \(K\) or more, it is sufficient to manage only \(K+1\) values for the number of completed jobs: “\(0, 1, 2, \dots, K\) (\(K\) or more).”

Algorithm

1. Preprocessing (Sorting) Sort the given \(N\) jobs in ascending order of deadline \(T_i\) (earliest first).

2. DP Table Definition Define \(dp[c][d]\) as “the maximum reward when \(c\) jobs have been completed and \(d\) days have elapsed.”

   • \(c\) ranges from \(0\) to \(K\) (\(K\) means “\(K\) or more”)
   • \(d\) ranges from \(0\) to \(M\)
   • The initial state is \(dp[0][0] = 0\), and all other states are set to a sufficiently small value (\(-\infty\)) to indicate they are unreachable.

3. DP Transitions We iterate through the sorted jobs in order, and for each job (duration \(D\), reward \(V\), deadline \(T\)), we update the DP table. From the current state \(dp[c][d]\), if we select this job, the next state becomes:

   • Number of completed jobs: \(\min(c + 1, K)\)
   • Elapsed days: \(d + D\)
   • Reward: \(dp[c][d] + V\)

However, the absolute condition for selecting a job is meeting the deadline. That is, a transition is only possible when \(d + D \leq T\) is satisfied. When the condition is met, we update \(dp[\min(c + 1, K)][d + D]\) with the maximum of its current value and the new reward.

1. Computing the Answer After processing all jobs, we search for the maximum value in the DP table.
   • When \(c < K\), \(dp[c][d]\) is the final reward as-is.
   • When \(c = K\), the bonus condition is satisfied, so \(dp[K][d] + B\) is the final reward. The largest among all of these is the answer.

Complexity

• Time complexity: \(O(N M K)\)
  • This involves a triple loop over the number of jobs \(N\), the completed job count states \(K\), and the elapsed days \(M\). The maximum computation is approximately \(200 \times 200 \times 5000 = 2 \times 10^8\) operations, but with optimizations such as skipping unreachable states, it comfortably fits within the time limit.
• Space complexity: \(O(M K)\)
  • Memory is needed to hold a 2D array of size \(K \times M\). At most this is about \(200 \times 5000 = 10^6\) elements, which is well within memory limits.

Implementation Notes

• Preventing the same job from being selected multiple times Similar to the 1D array implementation of the 0-1 knapsack problem, the loop over the number of completed jobs \(c\) must be iterated in descending order (from \(K-1\) down to \(0\)). Iterating in ascending order would cause a bug where the same job is selected more than once.

• Special handling of state \(K\) When adding a new job to a state where the number of completed jobs is already \(K\) or more (\(c = K\)), the transition destination is also \(c = K\). Therefore, in the correct code, the update for \(c = K\) is performed in a separate block.

• Python-specific optimizations If you implement \(O(N M K)\) with simple for loops in Python, there is a risk of exceeding the time limit (TLE). The correct code manages the maximum reachable days for each state using a max_d array to eliminate unnecessary computations, and achieves significant speedup by using list slicing and zip to perform batch array updates.

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    B = int(data[3])
    
    jobs = []
    idx = 4
    for _ in range(N):
        jobs.append((int(data[idx]), int(data[idx+1]), int(data[idx+2])))
        idx += 3
        
    # 納期が早い順にソート（区間スケジューリングの基本）
    jobs.sort(key=lambda x: x[2])
    
    MIN_INF = -10**18
    # dp[c][d] : 完了した仕事数が c 個（ただし K 個以上は K として扱う）、経過日数が d 日のときの最大報酬
    dp = [[MIN_INF] * (M + 1) for _ in range(K + 1)]
    dp[0][0] = 0
    
    # 各完了仕事数 c において、到達可能な最大日数を管理して無駄な計算を省く
    max_d = [-1] * (K + 1)
    max_d[0] = 0
    
    for D, V, T in jobs:
        limit = T - D
        if limit < 0:
            continue
            
        dp_K = dp[K]
        max_d_K = max_d[K]
        
        # 完了仕事数がすでに K 個以上の状態への仕事の追加
        if max_d_K != -1:
            end = limit if limit < max_d_K else max_d_K
            if end >= 0:
                dp_K[D : end + D + 1] = [
                    s + V if s + V > t else t
                    for t, s in zip(dp_K[D : end + D + 1], dp_K[: end + 1])
                ]
                if end + D > max_d[K]:
                    max_d[K] = end + D
                    
        # 完了仕事数が K 個未満の状態からの遷移
        for c in range(K - 1, -1, -1):
            max_d_c = max_d[c]
            if max_d_c != -1:
                end = limit if limit < max_d_c else max_d_c
                if end >= 0:
                    dp_c1 = dp[c + 1]
                    dp_c = dp[c]
                    dp_c1[D : end + D + 1] = [
                        s + V if s + V > t else t
                        for t, s in zip(dp_c1[D : end + D + 1], dp_c[: end + 1])
                    ]
                    if end + D > max_d[c + 1]:
                        max_d[c + 1] = end + D
                        
    ans = 0
    
    # ボーナス条件を満たさない場合の最大報酬
    for c in range(K):
        for val in dp[c]:
            if val > ans:
                ans = val
                
    # ボーナス条件を満たす場合の最大報酬
    for val in dp[K]:
        if val != MIN_INF:
            if val + B > ans:
                ans = val + B
                
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.