Overview

A problem of scheduling jobs with deadlines to maximize reward. Since a bonus is added when \(K\) or more jobs are completed, we also need to track the number of jobs.

Analysis

Key Insight ①: Validity of Sorting by Deadline

When selecting and scheduling multiple jobs, it is optimal to process them in order of earliest deadline (EDF: Earliest Deadline First). Intuitively, if we don’t finish jobs with earlier deadlines first, postponing them will cause us to miss their deadlines. This allows us to reduce the problem to a DP where we sort jobs by deadline and decide “select/don’t select” in order.

Key Insight ②: Handling the Bonus Condition

Since the bonus is obtained when \(K\) or more jobs are completed, we need to track “the number of completed jobs” as part of the DP state. However, since the bonus is the same \(B\) regardless of how many jobs are completed as long as it’s \(K\) or more, we can cap the job count at \(K\) (treating all values \(K\) or above the same).

Problem with the Naive Approach

Exhaustively searching all subsets of jobs gives \(2^N\) possibilities, which is infeasible for \(N=200\). We use DP, but if the state is only “time \(t\)”, we cannot determine the number of jobs and thus cannot judge the bonus condition.

Algorithm

DP Definition: \(dp[t][c]\) = maximum reward when \(t\) days of work time have been used so far and \(c\) jobs have been completed

• \(t\): \(0 \leq t \leq M\) (days used; the next job can start from day \(t+1\))
• \(c\): \(0 \leq c \leq K\) (number of completed jobs; capped at \(K\))

Procedure:

1. Sort jobs in ascending order of deadline \(T_i\)
2. Initial state: \(dp[0][0] = 0\), all others are \(-\infty\)
3. For each job \(i\) (after sorting), update in a 0-1 knapsack fashion:
   • Condition for starting job \(i\): with start day \(t+1\), the completion day \(t+D_i \leq T_i\), i.e., \(t \leq T_i - D_i\)
   • Transition: \(dp[t + D_i][\min(c+1, K)] \leftarrow \max(\cdot,\; dp[t][c] + V_i)\)
   • To avoid using the same job multiple times, iterate \(t\) from large to small (standard technique for 0-1 knapsack)
4. Finally, scan all states and add \(B\) if \(c \geq K\), then find the maximum value

Concrete Example: \(M=10\), Job A (\(D=3, V=5, T=5\)), Job B (\(D=2, V=3, T=8\)) - \(dp[0][0]=0\) → Select Job A → \(dp[3][1]=5\) → Select Job B → \(dp[5][2]=8\)

Complexity

• Time complexity: \(O(N \cdot M \cdot K)\)
  • Loop over \(N\) jobs × time \(M\) × count \(K\) state updates
  • Worst case: \(200 \times 5000 \times 200 = 2 \times 10^8\)
• Space complexity: \(O(M \cdot K)\)
  • DP table size: \((M+1) \times (K+1)\)

Implementation Notes

• Reverse iteration for 0-1 knapsack: Since each job can be used at most once, update time \(t\) from large to small. This prevents selecting the same job multiple times.

• Capping the count: By capping the job count \(c\) at \(K\), we limit the number of states. \(c = K\) means “\(K\) or more jobs completed”.

• Upper bound on feasible start time: \(t \leq T_i - D_i\) and \(t \leq M - D_i\) (since \(T_i \leq M\), the former dominates, but to prevent out-of-bounds array access, use min(max_t, M - D)).

• Fast input: In Python, use sys.stdin.buffer.read() to read all input at once for better speed.

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1
    
    jobs = []
    for i in range(N):
        D = int(input_data[idx]); idx += 1
        V = int(input_data[idx]); idx += 1
        T = int(input_data[idx]); idx += 1
        jobs.append((D, V, T))
    
    # Sort jobs by deadline (greedy scheduling: EDF ordering)
    jobs.sort(key=lambda x: x[2])
    
    # We need to track both total value and number of jobs completed.
    # Since bonus depends on whether count >= K, we need to know the count.
    # 
    # DP approach: dp[j][c] = max total value when current time is j and c jobs completed
    # But c can be up to N=200 and j up to M=5000, so dp table is 5001 * 201 which is ~1M entries.
    # With N=200 jobs, total operations ~ 200 * 5000 * 200 = 200M which might be tight in Python.
    #
    # Optimization: cap c at K since for bonus we only care if c >= K.
    # dp[j][c] for c = 0..K, where c=K means "K or more jobs completed"
    # This gives 5001 * (K+1) entries, and K <= 200, so still up to 1M * 200 = 200M in worst case.
    #
    # Let's try with capping at K.
    
    NEG_INF = -1
    
    # dp[t][c] = max value achievable, having used time up to t, with c jobs done
    # c is capped at K
    cap = K
    
    # Use 1D arrays for efficiency: dp[t][c]
    # dp is (M+1) x (cap+1)
    dp = [[NEG_INF] * (cap + 1) for _ in range(M + 1)]
    dp[0][0] = 0
    
    for job_idx in range(N):
        D, V, T = jobs[job_idx]
        # Process in reverse to avoid using same job twice
        # For each state (t, c), if we schedule this job starting at time t,
        # it finishes at t + D - 1, which must be <= T, i.e., t + D - 1 <= T => t <= T - D + 1
        # Also t + D - 1 <= M => t <= M - D + 1 (but T <= M so T - D + 1 <= M - D + 1)
        max_start = T - D + 1  # latest start time (0-indexed: day t+1 in 1-indexed)
        # Actually let me re-think indexing:
        # dp[t][c] means: the earliest available day is t (0-indexed meaning day t+1 is next available)
        # Wait, let me use: dp[t][c] = max value when all scheduled jobs finish by day t
        # and next job can start on day t+1 (1-indexed).
        # Actually simpler: t = current time used. Next job starts at day t+1.
        # Job starting at day t+1 finishes at day t+D. Need t+D <= T.
        # So t <= T - D.
        
        max_t = T - D  # max value of t such that starting at t+1 finishes at t+D <= T
        if max_t < 0:
            continue
        
        # Iterate t from max_t down to 0, c from cap down to 0
        for t in range(min(max_t, M - D), -1, -1):
            new_t = t + D
            for c in range(cap, -1, -1):
                if dp[t][c] == NEG_INF:
                    continue
                new_c = min(c + 1, cap)
                new_val = dp[t][c] + V
                if new_val > dp[new_t][new_c]:
                    dp[new_t][new_c] = new_val
    
    ans = 0
    for t in range(M + 1):
        for c in range(cap + 1):
            if dp[t][c] == NEG_INF:
                continue
            val = dp[t][c]
            if c >= K:
                val += B
            if val > ans:
                ans = val
    
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.