oj.uz

Submission #303081

# Submission time Handle Problem Language Result Execution time Memory
303081 2020-09-19T21:11:14 Z llaki Carnival Tickets (IOI20_tickets) Java 11
100 / 100
 2573 ms 118972 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;
    }

    long doTheJob(int[][] x, int k, int n, int m) {
        Tickets[] tickets = new Tickets[n];
        int[][] answer = new int[n][m];
        int[] until = new int[n], after = new int[n];
        // triples [color, index]
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
                (int[] a, int[] b) -> {
                    int col1 = a[0], i1 = a[1];
                    int col2 = b[0], i2 = b[1];
                    return x[col1][i1] != x[col2][i2] ? Integer.compare(x[col1][i1], x[col2][i2]) : col1 - col2;
                }
        );
        for (int i = 0; i < n; i++) {
            pq.add(new int[] { i, 0 });
        }
        for (int i = 0; i < k * (n / 2); i++) {
            int[] p = pq.poll();
            int col = p[0];
            until[col]++;
            p[1]++;
            if (p[1] < k) {
                pq.add(p);
            }
        }
        pq = new PriorityQueue<>(
                (int[] a, int[] b) -> {
                    int col1 = a[0], i1 = a[1];
                    int col2 = b[0], i2 = b[1];
                    return x[col1][i1] != x[col2][i2] ? -Integer.compare(x[col1][i1], x[col2][i2]) : -col1 + col2;
                }
        );
        Arrays.fill(after, m);
        for (int i = 0; i < n; i++) {
            if (until[i] >= m) {
                continue;
            }
            pq.add(new int[] { i, m - 1 });
        }
        for (int i = 0; i < k * (n / 2); i++) {
            int[] p = pq.poll();
            int col = p[0];
            if (m - p[1] + until[col] > k) continue;
            after[col] = p[1];
            p[1]--;
            if (p[1] >= until[col]) {
                pq.add(p);
            }
        }
        for (int i = 0; i < n; i++) {
            tickets[i] = new Tickets(i, x[i], until[i] - 1, after[i]);
            //System.out.println("Ticket " + i + ": " + (until[i] - 1) + " " + after[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--;
                        }
                    }
                }
            }
        }
        grader.allocate_tickets(answer);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < until[i]; j++) {
                ans -= x[i][j];
            }
            for (int j = after[i]; j < m; j++) {
                ans += x[i][j];
            }
        }
        return ans;
    }

    long doTheJob1(int[][] x, int k, int n, int m) {
        Tickets[] tickets = new Tickets[n];
        int[][] answer = new int[n][m];
        int[] until = new int[n];
        // triples [color, index]
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
                (int[] a, int[] b) -> {
                    int col1 = a[0], i1 = a[1];
                    int col2 = b[0], i2 = b[1];
                    return x[col1][i1] != x[col2][i2] ? Integer.compare(x[col1][i1], x[col2][i2]) : col1 - col2;
                }
        );
        for (int i = 0; i < n; i++) {
            pq.add(new int[] { i, 0 });
        }
        for (int i = 0; i < k * (n / 2); i++) {
            int[] p = pq.poll();
            int col = p[0];
            until[col]++;
            p[1]++;
            if (p[1] < m) {
                pq.add(p);
            }
        }
//        int[] after = new int[n];
//        PriorityQueue<int[]> pq1 = new PriorityQueue<int[]>(
//                (int[] a, int[] b) -> {
//                    int col1 = a[0], i1 = a[1];
//                    int col2 = b[0], i2 = b[1];
//                    return x[col1][i1] != x[col2][i2] ? -Integer.compare(x[col1][i1], x[col2][i2]) : -col1 + col2;
//                }
//        );
//        Arrays.fill(after, m - 1);
//        for (int i = 0; i < n; i++) {
//            if (until[i] == m) continue;
//            pq1.add(new int[] { i, m - 2 });
//        }
//        for (int i = 0; i < k * (n / 2); i++) {
//            int[] p = pq1.poll();
//            int col = p[0];
//            after[col]--;
//            p[1]--;
//            if (p[1] >= until[col] - 1) {
//                pq1.add(p);
//            }
//        }
        for (int i = 0; i < n; i++) {
            //tickets[i] = new Tickets(i, x[i], until[i] - 1, after[i] + 1);
            tickets[i] = new Tickets(i, x[i], until[i] - 1, 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--;
                        }
                    }
                }
            }
        }
        grader.allocate_tickets(answer);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < until[i]; j++) {
                ans -= x[i][j];
            }
            //for (int j = after[i] + 1; j < m; j++) {
            for (int j = until[i]; j < m; j++) {
                ans += x[i][j];
            }
        }
        return ans;
    }

    long find_maximum1(int k, int[][] x) {
        int n = x.length;
        int m = x[0].length;
        if (k <= m) return doTheJob(x, k, n, m);
        if (k == m) {
            Tickets[] tickets = new Tickets[n];
            int[][] answer = new int[n][m];
            int[] until = new int[n];
            // triples [color, index]
            PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
                    (int[] a, int[] b) -> {
                        int col1 = a[0], i1 = a[1];
                        int col2 = b[0], i2 = b[1];
                        return x[col1][i1] != x[col2][i2] ? Integer.compare(x[col1][i1], x[col2][i2]) : col1 - col2;
                    }
            );
            for (int i = 0; i < n; i++) {
                pq.add(new int[] { i, 0 });
            }
            for (int i = 0; i < k * (n / 2); i++) {
                int[] p = pq.poll();
                int col = p[0];
                until[col]++;
                p[1]++;
                if (p[1] < m) {
                    pq.add(p);
                }
            }
            for (int i = 0; i < n; i++) {
                tickets[i] = new Tickets(i, x[i], until[i] - 1, 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--;
                            }
                        }
                    }
                }
            }
            grader.allocate_tickets(answer);
            long ans = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < until[i]; j++) {
                    ans -= x[i][j];
                }
                for (int j = until[i]; j < m; j++) {
                    ans += x[i][j];
                }
            }
            return ans;
        }
        int[][] answer = new int[n][m];
        long[][] bal = new long[n][k + 1];
        for (int i = 0; i < n; i++) {
            bal[i][0] = 0;
            for (int j = m - 1; j >= m - k; j--) {
                bal[i][0] += x[i][j];
            }
            for (int j = 1; j <= k; j++) {
                bal[i][j] = bal[i][j - 1] - x[i][m - k + j - 1] - x[i][j - 1];
            }
        }
        int nk = n * k;
        long[][] dp = new long[n + 1][2 * nk + 1];
        for (int i = 0; i <= 2 * nk; i++) {
            dp[n][i] = Long.MIN_VALUE;
        }
        dp[n][nk] = 0;
        for (int pos = n - 1; pos >= 0; pos--) {
            for (int b = 0; b <= 2 * nk; b++) {
                dp[pos][b] = Long.MIN_VALUE;
                for (int y = 0; y <= k; y++) {
                    int newBal = b + y - (k - y);
                    if (newBal > 2 * nk || newBal < 0) continue;
                    if (dp[pos + 1][newBal] != Long.MIN_VALUE) {
                        dp[pos][b] = Math.max(dp[pos][b], dp[pos + 1][newBal] + bal[pos][y]);
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) Arrays.fill(answer[i], -1);
        int curBal = nk;
        long ans1 = 0;
        Tickets[] tickets = new Tickets[n];
        for (int i = 0; i < n; i++) {
            int take = -1;
            for (int y = 0; y <= k; y++) {
                int b = curBal + y - (k - y);
                if (b < 0 || b > 2 * nk) continue;
                if (dp[i + 1][b] != Long.MIN_VALUE && dp[i + 1][b] + bal[i][y] == dp[i][curBal]) {
                    take = y;
                    break;
                }
            }
            tickets[i] = new Tickets(i, x[i], take - 1, m - (k - take));
            curBal += take - (k - take);
            ans1 += bal[i][take];
        }
        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--;
                        }
                    }
                }
            }
        }
        grader.allocate_tickets(answer);
        return ans1;
    }

    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 215 ms 16332 KB Output is correct
2 Correct 223 ms 16052 KB Output is correct
3 Correct 215 ms 16228 KB Output is correct
4 Correct 214 ms 15736 KB Output is correct
5 Correct 207 ms 15240 KB Output is correct
6 Correct 238 ms 16784 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 16080 KB Output is correct
2 Correct 202 ms 15336 KB Output is correct
3 Correct 223 ms 16120 KB Output is correct
4 Correct 228 ms 16096 KB Output is correct
5 Correct 344 ms 22384 KB Output is correct
6 Correct 855 ms 79676 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 15716 KB Output is correct
2 Correct 209 ms 16356 KB Output is correct
3 Correct 218 ms 16224 KB Output is correct
4 Correct 255 ms 16972 KB Output is correct
5 Correct 440 ms 23324 KB Output is correct
6 Correct 1298 ms 114260 KB Output is correct
7 Correct 1498 ms 114520 KB Output is correct
8 Correct 298 ms 17056 KB Output is correct
9 Correct 214 ms 16236 KB Output is correct
10 Correct 227 ms 15688 KB Output is correct
11 Correct 196 ms 15944 KB Output is correct
12 Correct 386 ms 18724 KB Output is correct
13 Correct 494 ms 22240 KB Output is correct
14 Correct 522 ms 22532 KB Output is correct
15 Correct 1908 ms 118972 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 16100 KB Output is correct
2 Correct 217 ms 16144 KB Output is correct
3 Correct 196 ms 15480 KB Output is correct
4 Correct 278 ms 16992 KB Output is correct
5 Correct 598 ms 23868 KB Output is correct
6 Correct 365 ms 17744 KB Output is correct
7 Correct 350 ms 17724 KB Output is correct
8 Correct 1903 ms 117092 KB Output is correct
9 Correct 2370 ms 84456 KB Output is correct
10 Correct 2494 ms 85144 KB Output is correct
11 Correct 2430 ms 91084 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 16220 KB Output is correct
2 Correct 215 ms 15820 KB Output is correct
3 Correct 244 ms 16620 KB Output is correct
4 Correct 264 ms 17120 KB Output is correct
5 Correct 259 ms 17000 KB Output is correct
6 Correct 291 ms 16772 KB Output is correct
7 Correct 223 ms 15864 KB Output is correct
8 Correct 229 ms 16404 KB Output is correct
9 Correct 253 ms 16408 KB Output is correct
10 Correct 265 ms 16996 KB Output is correct
11 Correct 257 ms 16860 KB Output is correct
12 Correct 283 ms 16508 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 16220 KB Output is correct
2 Correct 215 ms 15820 KB Output is correct
3 Correct 244 ms 16620 KB Output is correct
4 Correct 264 ms 17120 KB Output is correct
5 Correct 259 ms 17000 KB Output is correct
6 Correct 291 ms 16772 KB Output is correct
7 Correct 223 ms 15864 KB Output is correct
8 Correct 229 ms 16404 KB Output is correct
9 Correct 253 ms 16408 KB Output is correct
10 Correct 265 ms 16996 KB Output is correct
11 Correct 257 ms 16860 KB Output is correct
12 Correct 283 ms 16508 KB Output is correct
13 Correct 388 ms 23752 KB Output is correct
14 Correct 325 ms 22552 KB Output is correct
15 Correct 441 ms 23396 KB Output is correct
16 Correct 537 ms 23836 KB Output is correct
17 Correct 260 ms 16488 KB Output is correct
18 Correct 278 ms 16272 KB Output is correct
19 Correct 267 ms 16788 KB Output is correct
20 Correct 502 ms 23628 KB Output is correct
21 Correct 550 ms 24048 KB Output is correct
22 Correct 595 ms 24440 KB Output is correct
23 Correct 496 ms 23992 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 16332 KB Output is correct
2 Correct 223 ms 16052 KB Output is correct
3 Correct 215 ms 16228 KB Output is correct
4 Correct 214 ms 15736 KB Output is correct
5 Correct 207 ms 15240 KB Output is correct
6 Correct 238 ms 16784 KB Output is correct
7 Correct 218 ms 16080 KB Output is correct
8 Correct 202 ms 15336 KB Output is correct
9 Correct 223 ms 16120 KB Output is correct
10 Correct 228 ms 16096 KB Output is correct
11 Correct 344 ms 22384 KB Output is correct
12 Correct 855 ms 79676 KB Output is correct
13 Correct 221 ms 15716 KB Output is correct
14 Correct 209 ms 16356 KB Output is correct
15 Correct 218 ms 16224 KB Output is correct
16 Correct 255 ms 16972 KB Output is correct
17 Correct 440 ms 23324 KB Output is correct
18 Correct 1298 ms 114260 KB Output is correct
19 Correct 1498 ms 114520 KB Output is correct
20 Correct 298 ms 17056 KB Output is correct
21 Correct 214 ms 16236 KB Output is correct
22 Correct 227 ms 15688 KB Output is correct
23 Correct 196 ms 15944 KB Output is correct
24 Correct 386 ms 18724 KB Output is correct
25 Correct 494 ms 22240 KB Output is correct
26 Correct 522 ms 22532 KB Output is correct
27 Correct 1908 ms 118972 KB Output is correct
28 Correct 213 ms 16100 KB Output is correct
29 Correct 217 ms 16144 KB Output is correct
30 Correct 196 ms 15480 KB Output is correct
31 Correct 278 ms 16992 KB Output is correct
32 Correct 598 ms 23868 KB Output is correct
33 Correct 365 ms 17744 KB Output is correct
34 Correct 350 ms 17724 KB Output is correct
35 Correct 1903 ms 117092 KB Output is correct
36 Correct 2370 ms 84456 KB Output is correct
37 Correct 2494 ms 85144 KB Output is correct
38 Correct 2430 ms 91084 KB Output is correct
39 Correct 209 ms 16220 KB Output is correct
40 Correct 215 ms 15820 KB Output is correct
41 Correct 244 ms 16620 KB Output is correct
42 Correct 264 ms 17120 KB Output is correct
43 Correct 259 ms 17000 KB Output is correct
44 Correct 291 ms 16772 KB Output is correct
45 Correct 223 ms 15864 KB Output is correct
46 Correct 229 ms 16404 KB Output is correct
47 Correct 253 ms 16408 KB Output is correct
48 Correct 265 ms 16996 KB Output is correct
49 Correct 257 ms 16860 KB Output is correct
50 Correct 283 ms 16508 KB Output is correct
51 Correct 388 ms 23752 KB Output is correct
52 Correct 325 ms 22552 KB Output is correct
53 Correct 441 ms 23396 KB Output is correct
54 Correct 537 ms 23836 KB Output is correct
55 Correct 260 ms 16488 KB Output is correct
56 Correct 278 ms 16272 KB Output is correct
57 Correct 267 ms 16788 KB Output is correct
58 Correct 502 ms 23628 KB Output is correct
59 Correct 550 ms 24048 KB Output is correct
60 Correct 595 ms 24440 KB Output is correct
61 Correct 496 ms 23992 KB Output is correct
62 Correct 456 ms 33712 KB Output is correct
63 Correct 480 ms 30048 KB Output is correct
64 Correct 731 ms 31596 KB Output is correct
65 Correct 972 ms 61460 KB Output is correct
66 Correct 1159 ms 62512 KB Output is correct
67 Correct 344 ms 17376 KB Output is correct
68 Correct 322 ms 17664 KB Output is correct
69 Correct 959 ms 80000 KB Output is correct
70 Correct 1652 ms 114308 KB Output is correct
71 Correct 1949 ms 88156 KB Output is correct
72 Correct 2452 ms 85288 KB Output is correct
73 Correct 2573 ms 84836 KB Output is correct
74 Correct 2054 ms 82944 KB Output is correct
75 Correct 2082 ms 83368 KB Output is correct