Submission #1047210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047210		n1k	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1247 ms	86864 KiB

tickets

#include "tickets.h"
#include <vector>

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n, m;
	n = x.size();
	m = x[0].size();

	vector<std::vector<int>> answer(n, vector<int>(m, -1));
	vector<deque<int>> sub(n), add(n);

	priority_queue<array<ll, 2>> pq;
	ll ans = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(j<k){
				sub[i].push_back(x[i][j]);
				ans -= x[i][j];
				answer[i][j] = -2;
			}else{
				add[i].push_back(x[i][j]);
			}
		}
		if(add[i].size()){
			pq.push({add[i].back() + sub[i].back(), i});
		}else{
			pq.push({2 * sub[i].back(), i});
		}
	}

	for(int i=0; i<n*k/2; i++){
		auto [val, id] = pq.top();
		pq.pop();
		ans += val;
		answer[id][sub[id].size()-1] = -1;
		answer[id][sub[id].size() + add[id].size() - 1] = -3;

		add[id].push_front(sub[id].back());
		sub[id].pop_back();
		add[id].pop_back();
		if(sub[id].size()){
			if(add[id].size())
				pq.push({add[id].back() + sub[id].back(), id});
			else
				pq.push({2 * sub[id].back(), id});
		}
	}


	multiset<array<int, 2>> ms;
	for(int i=0; i<n; i++){
		int bal = 0;
		for(int j=0; j<m; j++){
			if(answer[i][j]==-2){
				bal--;
			}else if(answer[i][j]==-3){
				bal++;
			}
		}
		ms.insert({bal, i});
	}


	for(int i=0; i<k; i++){
		multiset<array<int, 2>> nms;
		int take = 0;
		for(auto [bal, id]:ms){
			if(take<n/2){
				for(int j=0; j<m; j++){
					if(answer[id][j]==-2){
						answer[id][j]=i;
						break;
					}
				}
				nms.insert({bal+1, id});
			}else{
				for(int j=0; j<m; j++){
					if(answer[id][j]==-3){
						answer[id][j]=i;
						break;
					}
				}
				nms.insert({bal-1, id});
			}
			take++;
		}
		swap(ms, nms);
	}

	allocate_tickets(answer);
	return ans;
}

• 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