Submission #1220637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220637		boclobanchat	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	566 ms	84752 KiB

tickets

#include"tickets.h"
#include<bits/stdc++.h>
using namespace std;
long long find_maximum(int k,vector< vector<int> > x)
{
	int n=x.size(),m=x[0].size();
	vector< vector<int> > ans(n),vl(n),vr(n);
	vector< vector< pair<int,int> > > vi(n);
	priority_queue< pair< int,pair<int,int> >,vector< pair< int,pair<int,int> > >,greater< pair< int,pair<int,int> > > > pq;
	long long s=0;
	for(int i=0;i<n;i++)
	{
		vi[i].resize(m),ans[i].resize(m);
		for(int j=0;j<m;j++) vi[i][j]={x[i][j],j},ans[i][j]=-1;
		sort(vi[i].begin(),vi[i].end());
		for(int j=m-1;j>=m-k;j--) ans[i][vi[i][j].second]=0,s+=vi[i][j].first;
		pq.push({vi[i][0].first+vi[i][m-k].first,{i,0}});
	}
	for(int i=0;i<n/2*k;i++)
	{
		int x=pq.top().second.first,y=pq.top().second.second,val=pq.top().first;
		pq.pop(),s-=val,ans[x][vi[x][y].second]=0,ans[x][vi[x][m-k+y].second]=-1,vl[x].push_back(y);
		if(y+1<k) pq.push({vi[x][y+1].first+vi[x][m-k+y+1].first,{x,y+1}});
	}
	for(int i=0;i<n;i++)
	{
		int st=m-k;
		if(!vl[i].empty()) st=m-k+vl[i].back()+1;
		for(int j=st;j<m;j++) vr[i].push_back(j);
	}
	for(int i=0;i<k;i++)
	{
		vector<bool> ck(n);
		vector< pair<int,int> > vv;
		for(int j=0;j<n;j++) vv.push_back({vl[j].size(),j});
		sort(vv.begin(),vv.end(),greater< pair<int,int> >());
		for(int j=0;j<n;j++) if(j<n/2)
		{
			int pos=vv[j].second,py=vl[pos].back();
			ans[pos][vi[pos][py].second]=i,ck[pos]=true,vl[pos].pop_back();
		}
		else
		{
			int pos=vv[j].second,py=vr[pos].back();
			ans[pos][vi[pos][py].second]=i,ck[pos]=true,vr[pos].pop_back();
		}
	}
	allocate_tickets(ans);
	return s;
}

• 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