Submission #417000

#	Time	Username	Problem	Language	Result	Execution time	Memory
417000		KoD	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	944 ms	67988 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"

using ll = long long;

template <class T> using Vec = std::vector<T>;

ll find_maximum(int K, Vec<Vec<int>> X) {
	const int N = (int) X.size();
	const int M = (int) X[0].size();
	ll ret = 0;
	std::priority_queue<std::pair<int, int>> heap;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K; ++j) {
			ret -= X[i][j];
			heap.emplace(X[i][M - j - 1] + X[i][K - j - 1], i);
		}
	}
	Vec<int> up(N);
	for (int i = 0; i < N * K / 2; ++i) {
		const auto [a, k] = heap.top();
		heap.pop();
		ret += a;
		up[k] += 1;
	}
	Vec<Vec<int>> Y(N, Vec<int>(M, -1));
	int s = 0, t = K;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K - up[i]; ++j) {
			Y[i][j] = s;
			s += 1;
			if (s == K) {
				s = 0;
			}
		}
		for (int j = 0; j < up[i]; ++j) {
			t -= 1;
			Y[i][M - j - 1] = t;
			if (t == 0) {
				t = K;
			}
		}
	}
	allocate_tickets(Y);
	return ret;
}

• 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