oj.uz

Submission #824194

# Submission time Handle Problem Language Result Execution time Memory
824194 2023-08-13T17:41:01 Z Username_taken12 Cloud Computing (CEOI18_clo) Java 11
54 / 100
 3000 ms 14468 KB 
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]);
	}
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory 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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory 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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory 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

Subtask #4
0 / 18.0

# Verdict Execution time Memory 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 -

Subtask #5
0 / 18.0

# Verdict Execution time Memory 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 -

Subtask #6
0 / 10.0

# Verdict Execution time Memory 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 -