Submission #986410

#	Time	Username	Problem	Language	Result	Execution time	Memory
986410		Pyqe	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	727 ms	114544 KiB

tickets

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,m,fq[1569],od[1569][2];
pair<long long,long long> as[2250069];

long long find_maximum(int d,vector<vector<int>> a)
{
	long long i,j,u,p,e,z=0;
	vector<int> v;
	vector<vector<int>> sq;
	
	n=a.size();
	m=a[0].size();
	for(i=0;i<n;i++)
	{
		for(j=0;j<d;j++)
		{
			p=i*d+j;
			as[p]={a[i][j]+a[i][j+m-d],i};
		}
		od[i][1]=m-1;
		sq.push_back(v);
		for(j=0;j<m;j++)
		{
			sq[i].push_back(-1);
		}
	}
	sort(as,as+n*d);
	for(i=0;i<n*d/2;i++)
	{
		p=as[i].sc;
		fq[p]++;
	}
	for(i=0;i<d;i++)
	{
		for(j=0;j<n;j++)
		{
			as[j]={fq[j]-od[j][0],j};
		}
		sort(as,as+n,greater<pair<long long,long long>>());
		for(j=0;j<n;j++)
		{
			p=as[j].sc;
			e=j>=n/2;
			u=!e*2-1;
			z+=a[p][od[p][e]]*-u;
			sq[p][od[p][e]]=i;
			od[p][e]+=u;
		}
	}
	allocate_tickets(sq);
	return z;
}

• 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