import java.io.*;
import java.util.*;
public class clo {
static int val=2000;
public static void main(String[] args) throws IOException {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
ArrayList<int[]> t = new ArrayList<>();
int N = Integer.parseInt(r.readLine());
for(int i=0; i<N; i++)
{
StringTokenizer st = new StringTokenizer(r.readLine()); //cores clockspeed price
int[] add = new int[]{Integer.parseInt(st.nextToken()), -1*Integer.parseInt(st.nextToken()), -1*Integer.parseInt(st.nextToken())};
t.add(add);
}
int M = Integer.parseInt(r.readLine());
for(int i=0; i<M; i++){
StringTokenizer st = new StringTokenizer(r.readLine());
int[] add = new int[]{-1*Integer.parseInt(st.nextToken()), -1*Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
t.add(add);
}
Collections.sort(t, new Comp());
//for(int i=0; i<t.size(); i++)
// System.out.println(Arrays.toString(t.get(i)));
//long[][] dp = new long[N+M+1][val*50+1];
long[] prev = new long[val*50+1];
long[] curr = new long[val*50+1];
/*for(int i=0; i<N+M+1; i++)
for(int j=0; j<val*50+1; j++)
dp[i][j]=Long.MIN_VALUE/2;*/
for(int k=0; k<2000*50+1; k++){
prev[k]=Long.MIN_VALUE/2;
curr[k]=Long.MIN_VALUE/2;
}
prev[0]=0;
//dp[0][0]=0;
for(int i=0; i<N+M; i++){
for(int j=0; j<2000*50+1; j++){
if(prev[j]!=Long.MIN_VALUE/2&&((t.get(i)[0]+j)>=0)){
curr[j+t.get(i)[0]]=Math.max(curr[j+t.get(i)[0]], prev[j]+t.get(i)[2]);
}
curr[j]=Math.max(prev[j], curr[j]);
}
for(int k=0; k<2000*50+1; k++)
prev[k]=curr[k];
//prev=curr;
for(int k=0; k<2000*50+1; k++)
curr[k]=Long.MIN_VALUE/2;
/*for(int k=0; k<40; k++)
System.out.print(prev[k]+" ");
System.out.println();*/
}
long max=0;
for(int j=0; j<val*50+1; j++)
{
max=Math.max(prev[j], max);
}
pw.println(max);
pw.close();
}
}
class Comp implements Comparator<int[]>{
public int compare(int[] a , int[] b){
return Integer.compare(a[1], b[1]);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
102 ms |
12652 KB |
Output is correct |
2 |
Correct |
86 ms |
13004 KB |
Output is correct |
3 |
Correct |
122 ms |
12604 KB |
Output is correct |
4 |
Correct |
158 ms |
12808 KB |
Output is correct |
5 |
Correct |
732 ms |
14396 KB |
Output is correct |
6 |
Correct |
723 ms |
14468 KB |
Output is correct |
7 |
Correct |
666 ms |
13088 KB |
Output is correct |
8 |
Correct |
735 ms |
13372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
86 ms |
12744 KB |
Output is correct |
2 |
Correct |
100 ms |
13016 KB |
Output is correct |
3 |
Correct |
118 ms |
12680 KB |
Output is correct |
4 |
Correct |
122 ms |
12808 KB |
Output is correct |
5 |
Correct |
580 ms |
13056 KB |
Output is correct |
6 |
Correct |
382 ms |
13284 KB |
Output is correct |
7 |
Correct |
1856 ms |
13184 KB |
Output is correct |
8 |
Correct |
849 ms |
13132 KB |
Output is correct |
9 |
Correct |
2573 ms |
14060 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
95 ms |
12600 KB |
Output is correct |
2 |
Correct |
108 ms |
13172 KB |
Output is correct |
3 |
Correct |
143 ms |
13424 KB |
Output is correct |
4 |
Correct |
148 ms |
13004 KB |
Output is correct |
5 |
Correct |
199 ms |
12764 KB |
Output is correct |
6 |
Correct |
202 ms |
12904 KB |
Output is correct |
7 |
Correct |
272 ms |
12956 KB |
Output is correct |
8 |
Correct |
259 ms |
13348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
95 ms |
12792 KB |
Output is correct |
2 |
Correct |
91 ms |
12784 KB |
Output is correct |
3 |
Correct |
618 ms |
13168 KB |
Output is correct |
4 |
Correct |
649 ms |
13900 KB |
Output is correct |
5 |
Execution timed out |
3074 ms |
13708 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
86 ms |
12660 KB |
Output is correct |
2 |
Correct |
142 ms |
12972 KB |
Output is correct |
3 |
Correct |
555 ms |
13064 KB |
Output is correct |
4 |
Correct |
825 ms |
14436 KB |
Output is correct |
5 |
Execution timed out |
3066 ms |
13868 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
102 ms |
12652 KB |
Output is correct |
2 |
Correct |
86 ms |
13004 KB |
Output is correct |
3 |
Correct |
122 ms |
12604 KB |
Output is correct |
4 |
Correct |
158 ms |
12808 KB |
Output is correct |
5 |
Correct |
732 ms |
14396 KB |
Output is correct |
6 |
Correct |
723 ms |
14468 KB |
Output is correct |
7 |
Correct |
666 ms |
13088 KB |
Output is correct |
8 |
Correct |
735 ms |
13372 KB |
Output is correct |
9 |
Correct |
86 ms |
12744 KB |
Output is correct |
10 |
Correct |
100 ms |
13016 KB |
Output is correct |
11 |
Correct |
118 ms |
12680 KB |
Output is correct |
12 |
Correct |
122 ms |
12808 KB |
Output is correct |
13 |
Correct |
580 ms |
13056 KB |
Output is correct |
14 |
Correct |
382 ms |
13284 KB |
Output is correct |
15 |
Correct |
1856 ms |
13184 KB |
Output is correct |
16 |
Correct |
849 ms |
13132 KB |
Output is correct |
17 |
Correct |
2573 ms |
14060 KB |
Output is correct |
18 |
Correct |
95 ms |
12600 KB |
Output is correct |
19 |
Correct |
108 ms |
13172 KB |
Output is correct |
20 |
Correct |
143 ms |
13424 KB |
Output is correct |
21 |
Correct |
148 ms |
13004 KB |
Output is correct |
22 |
Correct |
199 ms |
12764 KB |
Output is correct |
23 |
Correct |
202 ms |
12904 KB |
Output is correct |
24 |
Correct |
272 ms |
12956 KB |
Output is correct |
25 |
Correct |
259 ms |
13348 KB |
Output is correct |
26 |
Correct |
95 ms |
12792 KB |
Output is correct |
27 |
Correct |
91 ms |
12784 KB |
Output is correct |
28 |
Correct |
618 ms |
13168 KB |
Output is correct |
29 |
Correct |
649 ms |
13900 KB |
Output is correct |
30 |
Execution timed out |
3074 ms |
13708 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |