Submission #304136

#	Time	Username	Problem	Language	Result	Execution time	Memory
304136		QAQAutoMaton	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1119 ms	84344 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
typedef std::pair<int,int> pii;
#define x first
#define y second
std::vector<pii> vt[1505];
int cur[1505],id[1505];
std::priority_queue<pii> pq;
void Push(int x,int k,int m){
	if(cur[x]>k)return;
	pq.push(std::make_pair(vt[x][k-cur[x]].x+vt[x][m-cur[x]].x,x));
}
std::vector<int> vd[1505],va[1505];
long long find_maximum(int k, std::vector<std::vector<int>> a) {
	int n = a.size();
	int m = a[0].size();
	std::vector<std::vector<int>> answer(n,std::vector<int>(m,-1));
	long long ans=0;
	for(int i=0;i<n;++i){
		vt[i].resize(m);
		for(int j=0;j<m;++j)vt[i][j]=std::make_pair(a[i][j],j);
		std::sort(vt[i].begin(),vt[i].end());
		for(int j=0;j<k;++j){ans-=vt[i][j].x;}
		cur[i]=1;
		Push(i,k,m);
	}
	int w=(n>>1)*k,hn=n>>1;
	for(int i=0;i<w;++i){
		ans+=pq.top().x;
		int id=pq.top().y;
		pq.pop();
		++cur[id];
		Push(id,k,m);
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<=k-cur[i];++j)vd[i].emplace_back(vt[i][j].y);
		for(int j=m-cur[i]+1;j<m;++j)va[i].emplace_back(vt[i][j].y);
		id[i]=i;
	}
	for(int i=0;i<k;++i){
		std::sort(id,id+n,[](int x,int y){return vd[x].size()<vd[y].size();});
		for(int j=0;j<hn;++j){
			answer[id[j]][va[id[j]].back()]=i;
			va[id[j]].pop_back();
		}
		for(int j=hn;j<n;++j){
			answer[id[j]][vd[id[j]].back()]=i;
			vd[id[j]].pop_back();
		}
	}
	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