Submission #302692

#	Time	Username	Problem	Language	Result	Execution time	Memory
302692		llaki	Carnival Tickets (IOI20_tickets)	Java	39 / 100	3125 ms	459564 KiB

tickets

import java.util.Arrays;

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];
        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;
//        TicketsWithColors[] plus = new TicketsWithColors[n];
//        TicketsWithColors[] minus = new TicketsWithColors[n];
        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;
                }
            }
//            for (int s = take - 1; s >= 0; s--) {
//                answer[i][s] = take - s - 1;
//            }
//            for (int s = m - 1; s >= m - (k - take); s--) {
//                answer[i][s] = take + (m - 1 - s);
//                // take - k
//            }
            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 < n; i++) {
            for (int j = 0; j < i; j++) {
                for (int a = 0; a <= tickets[i].minusTill; a++) {
                    for (int b = tickets[j].plusAfter; b <= m - 1; b++) {
                        if (tickets[i].val[a] > tickets[j].val[b]) {
                            return -1;
                        }
                    }
                }
            }
        }
        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: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10