oj.uz

Submission #483392

# Submission time Handle Problem Language Result Execution time Memory
483392 2021-10-29T05:41:45 Z ericpenguin Cloud Computing (CEOI18_clo) Java 11
54 / 100
 3000 ms 21260 KB 
import java.io.*;
import java.util.*;
public class clo {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<int[]> logs = new ArrayList<>();
        for (int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            logs.add(new int[]{0, 0, 0});
            logs.get(i)[0] = Integer.parseInt(st.nextToken());
            logs.get(i)[1] = Integer.parseInt(st.nextToken());
            logs.get(i)[2] = -Integer.parseInt(st.nextToken());
        }
        int m = Integer.parseInt(br.readLine());
        for (int i=N; i<m+N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            logs.add(new int[]{0, 0, 0});
            logs.get(i)[0] = -Integer.parseInt(st.nextToken());
            logs.get(i)[1] = Integer.parseInt(st.nextToken());
            logs.get(i)[2] = Integer.parseInt(st.nextToken());
        }
        Collections.sort(logs, (x, y) -> y[1]-x[1]);
        long[][] dp = new long[2][100001];
        Arrays.fill(dp[1], Long.MIN_VALUE);
        dp[1][0] = 0;
        for (int i=0; i<N+m; i++) {
            dp[i%2] = dp[1-i%2].clone();
            for (int c=0; c<=100000; c++) {
                if (c-logs.get(i)[0]<0 || c-logs.get(i)[0]>100000 || dp[1-i%2][c-logs.get(i)[0]]==Long.MIN_VALUE) continue;
                dp[i%2][c] = Math.max(dp[i%2][c], dp[1-i%2][c-logs.get(i)[0]] + logs.get(i)[2]);
            }
        }
        long ans = -1;
        for (int i=0; i<=100000; i++)
            ans = Math.max(ans, dp[(N+m-1)%2][i]);
        System.out.println(ans);
    }
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 15116 KB Output is correct
2 Correct 113 ms 15108 KB Output is correct
3 Correct 266 ms 18880 KB Output is correct
4 Correct 363 ms 18956 KB Output is correct
5 Correct 2383 ms 20448 KB Output is correct
6 Correct 2443 ms 20348 KB Output is correct
7 Correct 2538 ms 20360 KB Output is correct
8 Correct 2576 ms 20536 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 15008 KB Output is correct
2 Correct 125 ms 18080 KB Output is correct
3 Correct 236 ms 18900 KB Output is correct
4 Correct 273 ms 18964 KB Output is correct
5 Correct 1135 ms 19352 KB Output is correct
6 Correct 1191 ms 19216 KB Output is correct
7 Correct 2448 ms 20408 KB Output is correct
8 Correct 2524 ms 20488 KB Output is correct
9 Correct 2921 ms 19924 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 19064 KB Output is correct
2 Correct 176 ms 18864 KB Output is correct
3 Correct 321 ms 19012 KB Output is correct
4 Correct 331 ms 18920 KB Output is correct
5 Correct 525 ms 18940 KB Output is correct
6 Correct 494 ms 19100 KB Output is correct
7 Correct 737 ms 19260 KB Output is correct
8 Correct 781 ms 19268 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 18920 KB Output is correct
2 Correct 145 ms 18884 KB Output is correct
3 Correct 1921 ms 19512 KB Output is correct
4 Correct 2001 ms 20508 KB Output is correct
5 Execution timed out 3024 ms 21024 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 18116 KB Output is correct
2 Correct 307 ms 18760 KB Output is correct
3 Correct 1164 ms 19164 KB Output is correct
4 Correct 2457 ms 20316 KB Output is correct
5 Execution timed out 3053 ms 21260 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 15116 KB Output is correct
2 Correct 113 ms 15108 KB Output is correct
3 Correct 266 ms 18880 KB Output is correct
4 Correct 363 ms 18956 KB Output is correct
5 Correct 2383 ms 20448 KB Output is correct
6 Correct 2443 ms 20348 KB Output is correct
7 Correct 2538 ms 20360 KB Output is correct
8 Correct 2576 ms 20536 KB Output is correct
9 Correct 144 ms 15008 KB Output is correct
10 Correct 125 ms 18080 KB Output is correct
11 Correct 236 ms 18900 KB Output is correct
12 Correct 273 ms 18964 KB Output is correct
13 Correct 1135 ms 19352 KB Output is correct
14 Correct 1191 ms 19216 KB Output is correct
15 Correct 2448 ms 20408 KB Output is correct
16 Correct 2524 ms 20488 KB Output is correct
17 Correct 2921 ms 19924 KB Output is correct
18 Correct 176 ms 19064 KB Output is correct
19 Correct 176 ms 18864 KB Output is correct
20 Correct 321 ms 19012 KB Output is correct
21 Correct 331 ms 18920 KB Output is correct
22 Correct 525 ms 18940 KB Output is correct
23 Correct 494 ms 19100 KB Output is correct
24 Correct 737 ms 19260 KB Output is correct
25 Correct 781 ms 19268 KB Output is correct
26 Correct 135 ms 18920 KB Output is correct
27 Correct 145 ms 18884 KB Output is correct
28 Correct 1921 ms 19512 KB Output is correct
29 Correct 2001 ms 20508 KB Output is correct
30 Execution timed out 3024 ms 21024 KB Time limit exceeded
31 Halted 0 ms 0 KB -