Submission #524891

#	Time	Username	Problem	Language	Result	Execution time	Memory
524891		jamezzz	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	732 ms	92940 KiB

tickets

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

typedef long long ll;
typedef pair<int,int> ii;
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()

ll find_maximum(int k,vector<vector<int>> x){
	int n=x.size();
	int m=x[0].size();
	
	vector<vector<int>> answer(n);
	for(int i=0;i<n;++i)answer[i].resize(m,-1);
	
	ll ans=0;
	vector<int> npos(n);
	priority_queue<ii> pq;
	for(int i=0;i<n;++i){
		for(int j=0;j<k;++j){
			ans-=x[i][j];
			pq.push({x[i][m+j-k]+x[i][j],i});
		}
	}
	for(int i=0;i<n*k/2;++i){
		ans+=pq.top().fi;
		++npos[pq.top().se];
		pq.pop();
	}
	
	vector<vector<int>> have(k);
	for(int i=0;i<k;++i)have[i].resize(n);
	
	int cur=0;
	for(int i=0;i<n;++i){
		for(int j=m-1;j>=m-npos[i];--j){
			answer[i][j]=cur;
			have[cur][i]=1;
			cur=(cur+1)%k;
		}
	}
	
	for(int i=0;i<n;++i){
		int cur=0;
		for(int j=0;j<k;++j){
			if(!have[j][i]){
				answer[i][cur]=j;
				++cur;
			}
		}
	}
	
	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