Submission #301718

#	Time	Username	Problem	Language	Result	Execution time	Memory
301718		ijxjdjd	Carnival Tickets (IOI20_tickets)	Java	100 / 100	1660 ms	121260 KiB

tickets

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class tickets {
	long find_maximum(int K, int[][] x) {
		int N = x.length;
		int M = x[0].length;
		int S = (N*K)/2;
		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] ints, int[] t1) {
				return -Integer.compare(-x[ints[0]][ints[1]] - x[ints[0]][M - K + ints[1]], -x[t1[0]][t1[1]] - x[t1[0]][M-K+t1[1]]);
			}
		});
		for (int i = 0; i < N; i++) {
			queue.add(new int[]{i, 0});
		}
		int[] count = new int[N];
		for (int i = 0; i < S; i++) {
			int[] next = queue.remove();
			count[next[0]]++;
			if (next[1]+1 < K) {
				queue.add(new int[]{next[0], next[1] + 1});
			}
		}
		long res = 0;

		int[][] ans = new int[N][M];
		for (int i = 0; i < N; i++) {
			Arrays.fill(ans[i], -1);
		}
		int k = 0;
		for (int id = 0; id < N; id++) {
			int bef = k;
			if (count[id] == 0) {
				for (int c = 1; c <= K; c++) {
					ans[id][M-c] = k;
					res += x[id][M - c];
					k++;
					if (k == K) {
						k = 0;
					}
				}
			}
			else {
				for (int a = 0 ; a < count[id]; a++) {
					ans[id][a] = k;
					res -= x[id][a];
					k++;
					if (k == K) {
						k = 0;
					}
				}
				int c = 1;
				for (int i = k; i != bef; ) {
					res += x[id][M - c];
					ans[id][M-c] = i;
					c++;
					i++;
					if (i == K) {
						i = 0;
					}
				}
			}
		}

		grader.allocate_tickets(ans);
		return res;
	}

}

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