Submission #314592

#	Time	Username	Problem	Language	Result	Execution time	Memory
314592		kostia244	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	941 ms	60536 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<int> cnt(n, 0);
	ll cur = 0;
	for(int i = 0; i < n; i++) {
		for(int j = m-k; j < m; j++) {
			cur += x[i][j];
		}
	}
	auto cost = [&](int id, int lvl) {
		if(lvl == k) return -(1ll<<60);
		return ll(-x[id][lvl] -x[id][m-k+lvl]);
	};
	priority_queue<pair<ll, int>> a;
	for(int i = 0; i < n; i++) a.push({cost(i, 0), i});
	int need = n*k/2;
	while(need--) {
		auto [cst, i] = a.top();
		a.pop();
		cur += cst;
		a.push({cost(i, ++cnt[i]), i});
	}
	vector<vector<int>> res(n, vector<int>(m, -1));
	vector<int> ol;
	for(int lp = 0, rp = 0, i = 0; i < n; i++) {
		for(int j = 0; j < cnt[i]; j++) {
			res[i][j] = lp;
			lp = (lp+1)%k;
		}
		rp = lp;
		for(int j = m-k+cnt[i]; j < m; j++) {
			res[i][j] = rp;
			rp = (rp+1)%k;
		}
	}
	allocate_tickets(res);
	return cur;
}

• 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