oj.uz

Submission #303084

# Submission time Handle Problem Language Result Execution time Memory
303084 2020-09-19T21:15:42 Z llaki Carnival Tickets (IOI20_tickets) Java 11
100 / 100
 2581 ms 118840 KB 
import java.util.Arrays;
import java.util.PriorityQueue;

public class tickets {
    long find_maximum(int k, int[][] x) {
        int n = x.length;
        int m = x[0].length;
        int[][] answer = new int[n][m];
        for (int i = 0; i < n; i++) Arrays.fill(answer[i], -1);
        long ans = 0;
        // i -> m - k + i
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
            (int[] a, int[] b) -> {
            int col1 = a[0], i1 = a[1];
            int col2 = b[0], i2 = b[1];
            int s1 = x[col1][i1] + x[col1][m - k + i1];
            int s2 = x[col2][i2] + x[col2][m - k + i2];
            return s1 != s2 ? s1 - s2 : col1 - col2;
        });
        for (int i = 0; i < n; i++) {
            pq.add(new int[] { i, 0 });
        }
        int[] until = new int[n];
        for (int s = 0; s < k * (n / 2); s++) {
            int[] p = pq.poll();
            int col = p[0];
            int ind = p[1];
            until[col]++;
            if (ind < k - 1) {
                p[1]++;
                pq.add(p);
            }
        }
        Tickets[] tickets = new Tickets[n];
        for (int i = 0; i < n; i++) {
            tickets[i] = new Tickets(i, x[i], until[i] - 1, m - k + until[i]);
        }
        for (int i = 0; i < k; i++) {
            Arrays.sort(tickets, (Tickets a, Tickets b) -> Math.max(b.numMinus(), b.numPlus()) -
                    Math.max(a.numMinus(), a.numPlus()));
            int balance = 0;
            int numDaysLeft = k - i;
            for (int j = 0; j < n; j++) {
                Tickets t = tickets[j];
                int col = t.color;
                if (t.numMinus() == numDaysLeft) {
                    int index = t.minusTill;
                    t.minusTill--;
                    answer[col][index] = i;
                    balance--;
                } else if (t.numPlus() == numDaysLeft) {
                    int index = t.plusAfter;
                    t.plusAfter++;
                    answer[col][index] = i;
                    balance++;
                } else {
                    if (t.numMinus() == 0) {
                        int index = t.plusAfter;
                        t.plusAfter++;
                        answer[col][index] = i;
                        balance++;
                    } else if (t.numPlus() == 0) {
                        int index = t.minusTill;
                        t.minusTill--;
                        answer[col][index] = i;
                        balance--;
                    } else {
                        if (balance <= 0) {
                            int index = t.plusAfter;
                            t.plusAfter++;
                            answer[col][index] = i;
                            balance++;
                        } else {
                            int index = t.minusTill;
                            t.minusTill--;
                            answer[col][index] = i;
                            balance--;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < until[i]; j++) {
                ans -= x[i][j];
            }
            for (int j = until[i] + m - k; j < m; j++) {
                ans += x[i][j];
            }
        }
        grader.allocate_tickets(answer);
        return ans;
    }

    private class Tickets {
        int color;
        int[] val;
        int minusTill;
        int plusAfter;

        Tickets(int col, int[] val, int minusTill, int plusAfter) {
            this.color = col;
            this.val = val;
            this.minusTill = minusTill;
            this.plusAfter = plusAfter;
        }

        int numMinus() {
            return minusTill + 1;
        }

        int numPlus() {
            return val.length - plusAfter;
        }
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 16180 KB Output is correct
2 Correct 213 ms 16136 KB Output is correct
3 Correct 214 ms 15600 KB Output is correct
4 Correct 221 ms 16380 KB Output is correct
5 Correct 230 ms 16604 KB Output is correct
6 Correct 246 ms 15980 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 15480 KB Output is correct
2 Correct 212 ms 16232 KB Output is correct
3 Correct 212 ms 15984 KB Output is correct
4 Correct 241 ms 16048 KB Output is correct
5 Correct 337 ms 22612 KB Output is correct
6 Correct 889 ms 112756 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 16356 KB Output is correct
2 Correct 221 ms 15820 KB Output is correct
3 Correct 215 ms 15728 KB Output is correct
4 Correct 240 ms 16376 KB Output is correct
5 Correct 461 ms 23384 KB Output is correct
6 Correct 1292 ms 114296 KB Output is correct
7 Correct 1525 ms 115048 KB Output is correct
8 Correct 319 ms 17244 KB Output is correct
9 Correct 226 ms 16240 KB Output is correct
10 Correct 230 ms 15700 KB Output is correct
11 Correct 243 ms 16356 KB Output is correct
12 Correct 335 ms 18552 KB Output is correct
13 Correct 486 ms 23224 KB Output is correct
14 Correct 481 ms 22236 KB Output is correct
15 Correct 1861 ms 118840 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 16196 KB Output is correct
2 Correct 190 ms 15460 KB Output is correct
3 Correct 211 ms 15484 KB Output is correct
4 Correct 266 ms 16988 KB Output is correct
5 Correct 548 ms 23184 KB Output is correct
6 Correct 331 ms 17880 KB Output is correct
7 Correct 356 ms 17200 KB Output is correct
8 Correct 1964 ms 88036 KB Output is correct
9 Correct 2420 ms 107516 KB Output is correct
10 Correct 2291 ms 85672 KB Output is correct
11 Correct 2452 ms 91656 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 15592 KB Output is correct
2 Correct 270 ms 16656 KB Output is correct
3 Correct 242 ms 16484 KB Output is correct
4 Correct 253 ms 16236 KB Output is correct
5 Correct 264 ms 16872 KB Output is correct
6 Correct 246 ms 16244 KB Output is correct
7 Correct 238 ms 16264 KB Output is correct
8 Correct 227 ms 15480 KB Output is correct
9 Correct 253 ms 16992 KB Output is correct
10 Correct 250 ms 16736 KB Output is correct
11 Correct 297 ms 16808 KB Output is correct
12 Correct 271 ms 17252 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 15592 KB Output is correct
2 Correct 270 ms 16656 KB Output is correct
3 Correct 242 ms 16484 KB Output is correct
4 Correct 253 ms 16236 KB Output is correct
5 Correct 264 ms 16872 KB Output is correct
6 Correct 246 ms 16244 KB Output is correct
7 Correct 238 ms 16264 KB Output is correct
8 Correct 227 ms 15480 KB Output is correct
9 Correct 253 ms 16992 KB Output is correct
10 Correct 250 ms 16736 KB Output is correct
11 Correct 297 ms 16808 KB Output is correct
12 Correct 271 ms 17252 KB Output is correct
13 Correct 358 ms 22348 KB Output is correct
14 Correct 349 ms 22616 KB Output is correct
15 Correct 466 ms 23680 KB Output is correct
16 Correct 536 ms 24552 KB Output is correct
17 Correct 258 ms 16020 KB Output is correct
18 Correct 247 ms 16856 KB Output is correct
19 Correct 238 ms 16480 KB Output is correct
20 Correct 539 ms 23272 KB Output is correct
21 Correct 540 ms 23848 KB Output is correct
22 Correct 604 ms 24348 KB Output is correct
23 Correct 534 ms 23740 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 16180 KB Output is correct
2 Correct 213 ms 16136 KB Output is correct
3 Correct 214 ms 15600 KB Output is correct
4 Correct 221 ms 16380 KB Output is correct
5 Correct 230 ms 16604 KB Output is correct
6 Correct 246 ms 15980 KB Output is correct
7 Correct 228 ms 15480 KB Output is correct
8 Correct 212 ms 16232 KB Output is correct
9 Correct 212 ms 15984 KB Output is correct
10 Correct 241 ms 16048 KB Output is correct
11 Correct 337 ms 22612 KB Output is correct
12 Correct 889 ms 112756 KB Output is correct
13 Correct 212 ms 16356 KB Output is correct
14 Correct 221 ms 15820 KB Output is correct
15 Correct 215 ms 15728 KB Output is correct
16 Correct 240 ms 16376 KB Output is correct
17 Correct 461 ms 23384 KB Output is correct
18 Correct 1292 ms 114296 KB Output is correct
19 Correct 1525 ms 115048 KB Output is correct
20 Correct 319 ms 17244 KB Output is correct
21 Correct 226 ms 16240 KB Output is correct
22 Correct 230 ms 15700 KB Output is correct
23 Correct 243 ms 16356 KB Output is correct
24 Correct 335 ms 18552 KB Output is correct
25 Correct 486 ms 23224 KB Output is correct
26 Correct 481 ms 22236 KB Output is correct
27 Correct 1861 ms 118840 KB Output is correct
28 Correct 215 ms 16196 KB Output is correct
29 Correct 190 ms 15460 KB Output is correct
30 Correct 211 ms 15484 KB Output is correct
31 Correct 266 ms 16988 KB Output is correct
32 Correct 548 ms 23184 KB Output is correct
33 Correct 331 ms 17880 KB Output is correct
34 Correct 356 ms 17200 KB Output is correct
35 Correct 1964 ms 88036 KB Output is correct
36 Correct 2420 ms 107516 KB Output is correct
37 Correct 2291 ms 85672 KB Output is correct
38 Correct 2452 ms 91656 KB Output is correct
39 Correct 196 ms 15592 KB Output is correct
40 Correct 270 ms 16656 KB Output is correct
41 Correct 242 ms 16484 KB Output is correct
42 Correct 253 ms 16236 KB Output is correct
43 Correct 264 ms 16872 KB Output is correct
44 Correct 246 ms 16244 KB Output is correct
45 Correct 238 ms 16264 KB Output is correct
46 Correct 227 ms 15480 KB Output is correct
47 Correct 253 ms 16992 KB Output is correct
48 Correct 250 ms 16736 KB Output is correct
49 Correct 297 ms 16808 KB Output is correct
50 Correct 271 ms 17252 KB Output is correct
51 Correct 358 ms 22348 KB Output is correct
52 Correct 349 ms 22616 KB Output is correct
53 Correct 466 ms 23680 KB Output is correct
54 Correct 536 ms 24552 KB Output is correct
55 Correct 258 ms 16020 KB Output is correct
56 Correct 247 ms 16856 KB Output is correct
57 Correct 238 ms 16480 KB Output is correct
58 Correct 539 ms 23272 KB Output is correct
59 Correct 540 ms 23848 KB Output is correct
60 Correct 604 ms 24348 KB Output is correct
61 Correct 534 ms 23740 KB Output is correct
62 Correct 486 ms 30976 KB Output is correct
63 Correct 467 ms 33232 KB Output is correct
64 Correct 703 ms 33868 KB Output is correct
65 Correct 972 ms 61528 KB Output is correct
66 Correct 1134 ms 62428 KB Output is correct
67 Correct 347 ms 18004 KB Output is correct
68 Correct 356 ms 17720 KB Output is correct
69 Correct 968 ms 113272 KB Output is correct
70 Correct 1596 ms 86168 KB Output is correct
71 Correct 1856 ms 82792 KB Output is correct
72 Correct 2367 ms 113312 KB Output is correct
73 Correct 2581 ms 85084 KB Output is correct
74 Correct 2031 ms 109628 KB Output is correct
75 Correct 2087 ms 109016 KB Output is correct