Submission #308316

#	Time	Username	Problem	Language	Result	Execution time	Memory
308316		sofapuden	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	916 ms	54392 KiB

tickets

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

using namespace std;
typedef long long ll;

ll find_maximum(int k, vector<vector<int>> x) {
	priority_queue<pair<int,int>> PQ;
	ll n = x.size();
	ll m = x[0].size();
	vector<vector<int>> ans(n, vector<int> (m,-1));
	vector<int> go(n,0);
	ll out = 0;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < k; ++j){
			out-=x[i][j];
		}
		PQ.push({x[i][k-1]+x[i][m-1], i});
	}
	ll cn = 0;
	while(cn++ < (n/2)*k){
		auto now = PQ.top();
		out+=now.first;
		PQ.pop();
		if(++go[now.second] != k){
			PQ.push({x[now.second][k-1-go[now.second]]+x[now.second][m-1-go[now.second]],now.second});
		}
	}
	cn = 0;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < k-go[i]; ++j){
			ans[i][j] = cn++;
			cn%=k;
		}
		if(go[i] == 0)continue;
		int cn2 = cn;
		for(int j = m-go[i]; j < m; ++j){
			ans[i][j] = cn2++;
			cn2%=k;
		}
			
	}
	allocate_tickets(ans);
	
	return out;
}

• 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