Submission #770817

#	Time	Username	Problem	Language	Result	Execution time	Memory
770817		SanguineChameleon	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	601 ms	96052 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1.5e3 + 20;
vector<int> pos[maxn];
vector<int> neg[maxn];
int cnt[maxn];
int n, m, k;

void trace() {
	vector<vector<int>> res(n, vector<int>(m, -1));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < cnt[i]; j++) {
			pos[i].push_back(m - 1 - j);
		}
		for (int j = 0; j < k - cnt[i]; j++) {
			neg[i].push_back(j);
		}
	}
	for (int i = 0; i < k; i++) {
		int rem = n / 2;
		for (int j = 0; j < n; j++) {
			if (neg[j].empty()) {
				res[j][pos[j].back()] = i;
				pos[j].pop_back();
				rem--;
			}
		}
		for (int j = 0; j < n; j++) {
			if (!neg[j].empty()) {
				if (pos[j].empty() || rem == 0) {
					res[j][neg[j].back()] = i;
					neg[j].pop_back();
				}
				else {
					res[j][pos[j].back()] = i;
					pos[j].pop_back();
					rem--;
				}
			}
		}
	}
	allocate_tickets(res);
}

long long find_maximum(int _k, vector<vector<int>> a) {
	n = a.size();
	m = a[0].size();
	k = _k;
	vector<pair<int, int>> cost;
	long long res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= k; j++) {
			res -= a[i][j - 1];
			cost.emplace_back(a[i][k - j] + a[i][m - j], i);
		}
	}
	sort(cost.begin(), cost.end(), greater<pair<int, int>>());
	for (int i = 0; i < n / 2 * k; i++) {
		res += cost[i].first;
		cnt[cost[i].second]++;
	}
	trace();
	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