import java.util.*;
import java.io.*;
public class clo {
public static void main(String[] args) throws IOException{
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
ArrayList<int[]> possible = new ArrayList<>();
int max_Comp = 0;
int n = Integer.parseInt(r.readLine());
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(r.readLine());
int c = Integer.parseInt(st.nextToken()); int f = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken());
max_Comp += c;
possible.add(new int[]{c, f, -v});
}
int m = Integer.parseInt(r.readLine());
for (int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(r.readLine());
int c = Integer.parseInt(st.nextToken()); int f = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken());
possible.add(new int[]{-c, f, v});
}
Collections.sort(possible, (a, b) -> -Integer.compare(a[1], b[1]));
// Arrays.sort(orders, (a, b) -> -Integer.compare(a[1], b[1]));
long[] dp1 = new long[max_Comp + 1]; //number of transaction, the number of cores
long[] dp2 = new long[max_Comp + 1];
Arrays.fill(dp1, Long.MIN_VALUE); Arrays.fill(dp2, Long.MIN_VALUE);
dp1[0] = dp2[0] = 0;
for (int i = 0; i < n + m; i++) {
for (int j = 0; j <= max_Comp; j++) {
int prev_Cores = j - possible.get(i)[0];
if(0 <= prev_Cores && prev_Cores <= max_Comp && dp1[prev_Cores] != Long.MIN_VALUE){
dp2[j] = Math.max(dp2[j], dp1[prev_Cores] + possible.get(i)[2]);
}
}
for (int j = 0; j <= max_Comp; j++) {
dp1[j] = dp2[j];
}
}
long ans = 0;
for (int i = 0; i <= max_Comp; i++) {
ans = Math.max(ans, dp1[i]);
}
pw.println(ans);
pw.close();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
22792 KB |
Output is correct |
2 |
Correct |
57 ms |
22516 KB |
Output is correct |
3 |
Correct |
65 ms |
26520 KB |
Output is correct |
4 |
Correct |
79 ms |
23536 KB |
Output is correct |
5 |
Correct |
169 ms |
25760 KB |
Output is correct |
6 |
Correct |
149 ms |
25800 KB |
Output is correct |
7 |
Correct |
166 ms |
27812 KB |
Output is correct |
8 |
Correct |
193 ms |
26084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
22984 KB |
Output is correct |
2 |
Correct |
56 ms |
26684 KB |
Output is correct |
3 |
Correct |
95 ms |
26780 KB |
Output is correct |
4 |
Correct |
72 ms |
24168 KB |
Output is correct |
5 |
Correct |
231 ms |
28248 KB |
Output is correct |
6 |
Correct |
130 ms |
27160 KB |
Output is correct |
7 |
Correct |
676 ms |
31412 KB |
Output is correct |
8 |
Correct |
264 ms |
25944 KB |
Output is correct |
9 |
Correct |
1108 ms |
27088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
24256 KB |
Output is correct |
2 |
Correct |
55 ms |
22784 KB |
Output is correct |
3 |
Correct |
83 ms |
24408 KB |
Output is correct |
4 |
Correct |
81 ms |
23976 KB |
Output is correct |
5 |
Correct |
100 ms |
28140 KB |
Output is correct |
6 |
Correct |
95 ms |
28284 KB |
Output is correct |
7 |
Correct |
103 ms |
24592 KB |
Output is correct |
8 |
Correct |
102 ms |
23896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
22632 KB |
Output is correct |
2 |
Correct |
56 ms |
22476 KB |
Output is correct |
3 |
Correct |
169 ms |
24808 KB |
Output is correct |
4 |
Correct |
136 ms |
25524 KB |
Output is correct |
5 |
Correct |
1115 ms |
31076 KB |
Output is correct |
6 |
Correct |
1862 ms |
26932 KB |
Output is correct |
7 |
Correct |
1876 ms |
26560 KB |
Output is correct |
8 |
Correct |
1777 ms |
26416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
22616 KB |
Output is correct |
2 |
Correct |
95 ms |
24108 KB |
Output is correct |
3 |
Correct |
220 ms |
24308 KB |
Output is correct |
4 |
Correct |
186 ms |
25700 KB |
Output is correct |
5 |
Correct |
2175 ms |
27244 KB |
Output is correct |
6 |
Correct |
1875 ms |
26416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
22792 KB |
Output is correct |
2 |
Correct |
57 ms |
22516 KB |
Output is correct |
3 |
Correct |
65 ms |
26520 KB |
Output is correct |
4 |
Correct |
79 ms |
23536 KB |
Output is correct |
5 |
Correct |
169 ms |
25760 KB |
Output is correct |
6 |
Correct |
149 ms |
25800 KB |
Output is correct |
7 |
Correct |
166 ms |
27812 KB |
Output is correct |
8 |
Correct |
193 ms |
26084 KB |
Output is correct |
9 |
Correct |
55 ms |
22984 KB |
Output is correct |
10 |
Correct |
56 ms |
26684 KB |
Output is correct |
11 |
Correct |
95 ms |
26780 KB |
Output is correct |
12 |
Correct |
72 ms |
24168 KB |
Output is correct |
13 |
Correct |
231 ms |
28248 KB |
Output is correct |
14 |
Correct |
130 ms |
27160 KB |
Output is correct |
15 |
Correct |
676 ms |
31412 KB |
Output is correct |
16 |
Correct |
264 ms |
25944 KB |
Output is correct |
17 |
Correct |
1108 ms |
27088 KB |
Output is correct |
18 |
Correct |
54 ms |
24256 KB |
Output is correct |
19 |
Correct |
55 ms |
22784 KB |
Output is correct |
20 |
Correct |
83 ms |
24408 KB |
Output is correct |
21 |
Correct |
81 ms |
23976 KB |
Output is correct |
22 |
Correct |
100 ms |
28140 KB |
Output is correct |
23 |
Correct |
95 ms |
28284 KB |
Output is correct |
24 |
Correct |
103 ms |
24592 KB |
Output is correct |
25 |
Correct |
102 ms |
23896 KB |
Output is correct |
26 |
Correct |
56 ms |
22632 KB |
Output is correct |
27 |
Correct |
56 ms |
22476 KB |
Output is correct |
28 |
Correct |
169 ms |
24808 KB |
Output is correct |
29 |
Correct |
136 ms |
25524 KB |
Output is correct |
30 |
Correct |
1115 ms |
31076 KB |
Output is correct |
31 |
Correct |
1862 ms |
26932 KB |
Output is correct |
32 |
Correct |
1876 ms |
26560 KB |
Output is correct |
33 |
Correct |
1777 ms |
26416 KB |
Output is correct |
34 |
Correct |
57 ms |
22616 KB |
Output is correct |
35 |
Correct |
95 ms |
24108 KB |
Output is correct |
36 |
Correct |
220 ms |
24308 KB |
Output is correct |
37 |
Correct |
186 ms |
25700 KB |
Output is correct |
38 |
Correct |
2175 ms |
27244 KB |
Output is correct |
39 |
Correct |
1875 ms |
26416 KB |
Output is correct |
40 |
Correct |
271 ms |
25364 KB |
Output is correct |
41 |
Correct |
518 ms |
26264 KB |
Output is correct |
42 |
Correct |
214 ms |
26572 KB |
Output is correct |
43 |
Correct |
1521 ms |
26444 KB |
Output is correct |
44 |
Correct |
1550 ms |
26908 KB |
Output is correct |
45 |
Correct |
1731 ms |
26540 KB |
Output is correct |
46 |
Correct |
162 ms |
25768 KB |
Output is correct |
47 |
Correct |
202 ms |
29596 KB |
Output is correct |
48 |
Correct |
207 ms |
26596 KB |
Output is correct |