Submission #336982

#	Time	Username	Problem	Language	Result	Execution time	Memory
336982		zlxFTH	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1145 ms	66496 KiB

tickets

#include "tickets.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define Dval(c, i) d[c][O[c][i]]
using namespace std;

typedef long long LL;
typedef vector<int> Vec;
typedef pair<LL, LL> Pii;

LL find_maximum(int k, vector<Vec> d) {
	LL n = d.size(), m = d[0].size();
	vector<Vec> O(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) O[i].push_back(j);
		sort(O[i].begin(), O[i].end(), [&](int a, int b) { return d[i][a] < d[i][b]; });
	}
	LL prize = 0;
	Vec plus(n, 0), minus(n, 0), take(n, 0);
	priority_queue<Pii> Q;
	for (int c = 0; c < n; ++c) {
		for (int j = 0; j < k; ++j) prize -= Dval(c, j);
		Q.push(make_pair(Dval(c, k - 1) + Dval(c, m - 1), c));
	}
	for (int i = 0; i < n * k / 2; ++i) {
		Pii it = Q.top(); Q.pop();
		prize += it.first;
		int c = it.second, &pc = plus[c];
		if (++pc < k) Q.push(make_pair(Dval(c, k - 1 - pc) + Dval(c, m - 1 - pc), c));
	}
	while (!Q.empty()) Q.pop();
	for (int c = 0; c < n; ++c) Q.push(make_pair(plus[c], c));
	vector<Vec> S(n, Vec(m, -1));
	for (int ki = 0; ki < k; ++ki) {
		for (int i = 0; i < n / 2; ++i) take[Q.top().second] = 1, Q.pop();
		for (int c = 0; c < n; ++c) {
			int &p = plus[c];
			Vec &s = S[c];
			if (take[c]) s[O[c][m - p]] = ki, Q.push(make_pair(--p, c)), take[c] = 0;
			else s[O[c][minus[c]++]] = ki;
		}
	}
	allocate_tickets(S);
	return prize;
}

• 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