Each job has a deadline D, duration C, and reward S. Sort the jobs by deadline and process them in that order. Let dp[t] be the maximum reward of a schedule that finishes by time t.
For each job, consider taking it by updating dp[t] = max(dp[t], dp[t - C] + S) for t from D down to C. The jobs can be scheduled in deadline order: if two adjacent jobs are out of order, swapping them puts the earlier-deadline job first; its completion only gets earlier, while the second job’s completion time stays the same, so neither deadline is violated. Since deadlines are nondecreasing, all previously processed jobs have deadlines no later than the current one. Appending the current job to any feasible earlier-job schedule that finishes by t - C therefore meets its deadline whenever t <= D. This exchange argument shows that considering jobs in deadline order loses no feasible selection.
Iterating t downward ensures dp[t - C] still describes a schedule before the current job was considered, so the same job cannot be selected more than once. After each job, propagate prefix maxima (dp[t] = max(dp[t], dp[t - 1])) so the state means “finishes by time t,” not “uses exactly t time.” The answer is the maximum value in dp. With Dmax the largest deadline, the time complexity is O(N * Dmax) and the space complexity is O(Dmax).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import java.io.*;
import java.util.*;
public class Main {
static class FastScanner {
private final InputStream input;
private final byte[] buffer = new byte[1 << 16];
private int length = 0;
private int pointer = 0;
FastScanner(InputStream input) {
this.input = input;
}
private int read() throws IOException {
if (pointer == length) {
length = input.read(buffer);
pointer = 0;
if (length == -1) return -1;
}
return buffer[pointer++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
long nextLong() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
long value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
static class Job {
int deadline;
int duration;
long reward;
Job(int deadline, int duration, long reward) {
this.deadline = deadline;
this.duration = duration;
this.reward = reward;
}
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner(System.in);
int n = input.nextInt();
Job[] jobs = new Job[n];
int maxDeadline = 0;
for (int i = 0; i < n; i++) {
int deadline = input.nextInt();
int duration = input.nextInt();
long reward = input.nextLong();
jobs[i] = new Job(deadline, duration, reward);
maxDeadline = Math.max(maxDeadline, deadline);
}
Arrays.sort(jobs, Comparator.comparingInt(job -> job.deadline));
long[] dp = new long[maxDeadline + 1];
for (Job job : jobs) {
for (int time = job.deadline; time >= job.duration; time--) {
dp[time] = Math.max(dp[time], dp[time - job.duration] + job.reward);
}
for (int time = 1; time <= maxDeadline; time++) {
dp[time] = Math.max(dp[time], dp[time - 1]);
}
}
long answer = 0;
for (long reward : dp) {
answer = Math.max(answer, reward);
}
System.out.println(answer);
}
}