Submission #302818

#	Time	Username	Problem	Language	Result	Execution time	Memory
302818		llaki	Carnival Tickets (IOI20_tickets)	Java	25 / 100	2571 ms	120360 KiB

tickets

import java.util.Arrays;
import java.util.PriorityQueue;

public class tickets {
    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];
        // 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);
        for (int i = 0; i < n; i++) {
            if (until[i] == m) continue;
            pq1.add(new int[] { i, m - 1 });
        }
        for (int i = 0; i < k * (n / 2); i++) {
            int[] p = pq1.poll();
            int col = p[0];
            after[col] = p[1];
            p[1]--;
            if (p[1] >= until[col]) {
                pq1.add(p);
            }
        }
        for (int i = 0; i < n; i++) {
            tickets[i] = new Tickets(i, x[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 find_maximum(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;
        }
    }

    private class TicketsWithColors {
        int color;
        int[] val;
        int from;
        int to;

        TicketsWithColors(int color, int[] val, int l, int r) {
            this.color = color;
            this.val = val;
            this.from = l;
            this.to = r;
        }
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10