import java.io.*;
import java.util.*;
public class clo {
public static void main(String[] args) throws IOException {
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer l1 = new StringTokenizer(scan.readLine());
int n = Integer.parseInt(l1.nextToken());
int[][] arr1 = new int[n][3];
for (int i = 0;i<n;i++) {
StringTokenizer st = new StringTokenizer(scan.readLine());
arr1[i][0] = Integer.parseInt(st.nextToken()); arr1[i][1] = Integer.parseInt(st.nextToken()); arr1[i][2] = Integer.parseInt(st.nextToken());
}
StringTokenizer l2 = new StringTokenizer(scan.readLine());
int m = Integer.parseInt(l2.nextToken());
int[][] arr2 = new int[m][3];
for (int i = 0;i<m;i++) {
StringTokenizer st = new StringTokenizer(scan.readLine());
arr2[i][0] = Integer.parseInt(st.nextToken()); arr2[i][1] = Integer.parseInt(st.nextToken()); arr2[i][2] = Integer.parseInt(st.nextToken());
}
int num = n+m;
int[][] arr = new int[num][3];
for (int i = 0;i<n;i++) {
arr[i][0] = arr1[i][0]; arr[i][1] = arr1[i][1]; arr[i][2] = (-1)*arr1[i][2];
}
for (int i = 0;i<m;i++) {
arr[i+n][0] = (-1)*arr2[i][0]; arr[i+n][1] = arr2[i][1]; arr[i+n][2] = arr2[i][2];
}
Arrays.sort(arr, (a,b)->b[1]!=a[1] ? b[1]-a[1] : a[2]-b[2]);
//printMat(arr);
//Now just classic Knapsack
int maxC = n*50+1; //Max number of cores possible
long[] dp1 = new long[maxC]; long[] dp2 = new long[maxC];
Arrays.fill(dp1,Long.MIN_VALUE);
Arrays.fill(dp2,Long.MIN_VALUE);
dp1[0] = 0; dp2[0] = 0;
if (arr[0][0]>=0)
dp1[arr[0][0]] = arr[0][2];
for (int i = 1;i<num;i++) {
if (arr[i][0]>=0) {
dp2[arr[i][0]] = arr[i][2];
}
for (int j = 0;j<maxC;j++) {
dp2[j] = Math.max(dp2[j],dp1[j]);
if (maxC>j-arr[i][0]&&j-arr[i][0]>=0) {
if (dp1[j-arr[i][0]]!=Long.MIN_VALUE) {
dp2[j] = Math.max(dp2[j], dp1[j - arr[i][0]] + arr[i][2]);
}
}
}
for (int j = 0;j<maxC;j++) {
dp1[j] = dp2[j];
if (j==0)
dp2[0] = 0;
else
dp2[j] = Long.MIN_VALUE;
}
}
long ans = 0;
for (int j = 0;j<maxC;j++) {
ans = Math.max(ans,dp1[j]);
}
System.out.println(ans);
}
public static void printMat (int[][] arr) {
for (int i = 0;i<arr.length;i++) {
for (int j = 0;j<arr[0].length;j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
}
public static void printMat (long[][] arr) {
for (int i = 0;i<arr.length;i++) {
for (int j = 0;j<arr[0].length;j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
8728 KB |
Output is correct |
2 |
Correct |
54 ms |
8928 KB |
Output is correct |
3 |
Correct |
73 ms |
10352 KB |
Output is correct |
4 |
Correct |
85 ms |
10048 KB |
Output is correct |
5 |
Correct |
165 ms |
12708 KB |
Output is correct |
6 |
Correct |
166 ms |
12436 KB |
Output is correct |
7 |
Correct |
174 ms |
12812 KB |
Output is correct |
8 |
Correct |
206 ms |
12868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
8976 KB |
Output is correct |
2 |
Correct |
55 ms |
8712 KB |
Output is correct |
3 |
Correct |
79 ms |
10316 KB |
Output is correct |
4 |
Correct |
80 ms |
10632 KB |
Output is correct |
5 |
Correct |
299 ms |
11664 KB |
Output is correct |
6 |
Correct |
298 ms |
11624 KB |
Output is correct |
7 |
Correct |
986 ms |
13688 KB |
Output is correct |
8 |
Correct |
921 ms |
13488 KB |
Output is correct |
9 |
Correct |
861 ms |
13256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
9992 KB |
Output is correct |
2 |
Correct |
65 ms |
10316 KB |
Output is correct |
3 |
Correct |
89 ms |
10624 KB |
Output is correct |
4 |
Correct |
95 ms |
10768 KB |
Output is correct |
5 |
Correct |
109 ms |
10668 KB |
Output is correct |
6 |
Correct |
104 ms |
10580 KB |
Output is correct |
7 |
Correct |
152 ms |
11096 KB |
Output is correct |
8 |
Correct |
133 ms |
10612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
8740 KB |
Output is correct |
2 |
Correct |
67 ms |
8808 KB |
Output is correct |
3 |
Correct |
557 ms |
13236 KB |
Output is correct |
4 |
Correct |
140 ms |
12188 KB |
Output is correct |
5 |
Correct |
1722 ms |
14812 KB |
Output is correct |
6 |
Correct |
1813 ms |
14284 KB |
Output is correct |
7 |
Correct |
1845 ms |
14252 KB |
Output is correct |
8 |
Correct |
1780 ms |
14436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
8772 KB |
Output is correct |
2 |
Correct |
92 ms |
10780 KB |
Output is correct |
3 |
Correct |
208 ms |
11044 KB |
Output is correct |
4 |
Correct |
481 ms |
13088 KB |
Output is correct |
5 |
Correct |
1929 ms |
15016 KB |
Output is correct |
6 |
Correct |
1810 ms |
14372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
8728 KB |
Output is correct |
2 |
Correct |
54 ms |
8928 KB |
Output is correct |
3 |
Correct |
73 ms |
10352 KB |
Output is correct |
4 |
Correct |
85 ms |
10048 KB |
Output is correct |
5 |
Correct |
165 ms |
12708 KB |
Output is correct |
6 |
Correct |
166 ms |
12436 KB |
Output is correct |
7 |
Correct |
174 ms |
12812 KB |
Output is correct |
8 |
Correct |
206 ms |
12868 KB |
Output is correct |
9 |
Correct |
55 ms |
8976 KB |
Output is correct |
10 |
Correct |
55 ms |
8712 KB |
Output is correct |
11 |
Correct |
79 ms |
10316 KB |
Output is correct |
12 |
Correct |
80 ms |
10632 KB |
Output is correct |
13 |
Correct |
299 ms |
11664 KB |
Output is correct |
14 |
Correct |
298 ms |
11624 KB |
Output is correct |
15 |
Correct |
986 ms |
13688 KB |
Output is correct |
16 |
Correct |
921 ms |
13488 KB |
Output is correct |
17 |
Correct |
861 ms |
13256 KB |
Output is correct |
18 |
Correct |
67 ms |
9992 KB |
Output is correct |
19 |
Correct |
65 ms |
10316 KB |
Output is correct |
20 |
Correct |
89 ms |
10624 KB |
Output is correct |
21 |
Correct |
95 ms |
10768 KB |
Output is correct |
22 |
Correct |
109 ms |
10668 KB |
Output is correct |
23 |
Correct |
104 ms |
10580 KB |
Output is correct |
24 |
Correct |
152 ms |
11096 KB |
Output is correct |
25 |
Correct |
133 ms |
10612 KB |
Output is correct |
26 |
Correct |
59 ms |
8740 KB |
Output is correct |
27 |
Correct |
67 ms |
8808 KB |
Output is correct |
28 |
Correct |
557 ms |
13236 KB |
Output is correct |
29 |
Correct |
140 ms |
12188 KB |
Output is correct |
30 |
Correct |
1722 ms |
14812 KB |
Output is correct |
31 |
Correct |
1813 ms |
14284 KB |
Output is correct |
32 |
Correct |
1845 ms |
14252 KB |
Output is correct |
33 |
Correct |
1780 ms |
14436 KB |
Output is correct |
34 |
Correct |
56 ms |
8772 KB |
Output is correct |
35 |
Correct |
92 ms |
10780 KB |
Output is correct |
36 |
Correct |
208 ms |
11044 KB |
Output is correct |
37 |
Correct |
481 ms |
13088 KB |
Output is correct |
38 |
Correct |
1929 ms |
15016 KB |
Output is correct |
39 |
Correct |
1810 ms |
14372 KB |
Output is correct |
40 |
Correct |
271 ms |
12272 KB |
Output is correct |
41 |
Correct |
457 ms |
13180 KB |
Output is correct |
42 |
Correct |
1043 ms |
14404 KB |
Output is correct |
43 |
Correct |
1760 ms |
14780 KB |
Output is correct |
44 |
Correct |
1725 ms |
14928 KB |
Output is correct |
45 |
Correct |
1773 ms |
14552 KB |
Output is correct |
46 |
Correct |
519 ms |
14340 KB |
Output is correct |
47 |
Correct |
973 ms |
13812 KB |
Output is correct |
48 |
Correct |
984 ms |
14328 KB |
Output is correct |