Submission #301915

#	Time	Username	Problem	Language	Result	Execution time	Memory
301915		llaki	Carnival Tickets (IOI20_tickets)	Java	0 / 100	83 ms	10352 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++) {
            long sumSuffix = 0;
            for (int j = m - 1; j >= m - k; j--) {
                sumSuffix += x[i][j];
            }
            bal[i][0] = sumSuffix;
            for (int j = 1; j <= k; j++) {
                sumSuffix -= x[i][m - k + j - 1];
                bal[i][j] = -x[i][j - 1] + sumSuffix;
            }
        }
        int mk = m * k;
        long[][] dp = new long[n + 1][2 * mk + 1];
        for (int i = 0; i <= 2 * mk; i++) {
            dp[n][i] = Long.MIN_VALUE;
        }
        dp[n][mk] = 0;
        for (int pos = n - 1; pos >= 0; pos--) {
            for (int b = 0; b <= 2 * mk; b++) {
                dp[pos][b] = Long.MIN_VALUE;
                for (int y = 0; y <= k; y++) {
                    int newBal = b - mk + y - (k - y);
                    if (Math.abs(newBal) > mk) continue;
                    if (dp[pos + 1][newBal + mk] != Long.MIN_VALUE) {
                        dp[pos][b] = Math.max(dp[pos][b], dp[pos + 1][newBal + mk] + bal[pos][y]);
                    }
                }
            }
        }
        long ans = 0;
        for (int i = 0; i < n; i++) Arrays.fill(answer[i], -1);
        int curBal = 0;
        for (int i = n - 1; i >= 0; i--) {
            int take = -1;
            for (int y = 0; y <= k; y++) {
                int newBal = curBal + y - (k - y);
                if (Math.abs(newBal) > mk) continue;
                if (dp[i + 1][newBal + mk] != Long.MIN_VALUE && dp[i + 1][newBal + mk] + bal[i][y] == dp[i][curBal + mk]) {
                    take = y;
                    break;
                }
            }
            for (int s = 0; s < take; s++) {
                answer[i][s] = s;
            }
            for (int s = m - 1; s >= m - (k - take); s++) {
                answer[i][s] = s - (m - k);
            }
            curBal = curBal + take - (k - take);
        }
//        for (int a = 0; a < k; a++) {
//            for (int i = 0; i < n; i++) {
//                int col = t[i].color;
//                if (i < n / 2) {
//                    answer[col][t[i].from] = a;
//                    ans -= t[i].val[t[i].from];
//                    t[i].from++;
//                } else {
//                    answer[col][t[i].to] = a;
//                    ans += t[i].val[t[i].to];
//                    t[i].to--;
//                }
//            }
//        }
        //grader.allocate_tickets(answer);
        return ans;
    }

//    private class TicketsWithColors {
//        int color;
//        int[] val;
//        int from;
//        int to;
//
//        TicketsWithColors(int color, int[] val) {
//            this.color = color;
//            this.val = val;
//            this.from = 0;
//            this.to = val.length - 1;
//        }
//    }

//    long find_maximum(int k, int[][] x) {
//        int n = x.length;
//        int m = x[0].length;
//        int[][] answer = new int[n][m];
//        TicketsWithColors[] t = new TicketsWithColors[n];
//        for (int i = 0; i < n; i++) {
//            t[i] = new TicketsWithColors(i, x[i]);
//        }
//        long ans = 0;
//        for (int i = 0; i < n; i++) Arrays.fill(answer[i], -1);
//        for (int a = 0; a < k; a++) {
//            Arrays.sort(t, (t1, t2) ->
//                    t1.val[t1.from] + t1.val[t1.to] - t2.val[t2.from] - t2.val[t2.to]);
//            for (int i = 0; i < n; i++) {
//                int col = t[i].color;
//                if (i < n / 2) {
//                    answer[col][t[i].from] = a;
//                    ans -= t[i].val[t[i].from];
//                    t[i].from++;
//                } else {
//                    answer[col][t[i].to] = a;
//                    ans += t[i].val[t[i].to];
//                    t[i].to--;
//                }
//            }
//        }
//        //grader.allocate_tickets(answer);
//        return ans;
//    }


}

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