Submission #824194

#TimeUsernameProblemLanguageResultExecution timeMemory
824194Username_taken12Cloud Computing (CEOI18_clo)Java
54 / 100
3074 ms14468 KiB

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]);
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...