Submission #1039692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039692		amirhoseinfar1385	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	443 ms	94008 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1500+10;
long long n,m,all[maxn][maxn],last[maxn],av[maxn],akh[maxn],tof[maxn];
vector<vector<int>>res;

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	n = x.size();
	m = x[0].size();
	res.resize(n,vector<int>(m));
	for(long long i=0;i<n;i++){
		for(long long j=0;j<m;j++){
			all[i][j]=x[i][j];
			res[i][j]=-1;
		}
	}
	long long mainres=0;
	priority_queue<pair<long long,long long>>pq;
	for(int i=0;i<n;i++){
		for(int j=m-1;j>=m-k;j--){
			res[i][j]=1;
			mainres+=all[i][j];
		}
		pq.push(make_pair(-all[i][m-k]-all[i][0],i));
	}
	for(int i=0;i<(n*k)/2;i++){
		mainres+=pq.top().first;
		auto x=pq.top().second;
		pq.pop();
		res[x][last[x]]=1;
		res[x][m-k+last[x]]=-1;
		last[x]++;
		if(last[x]==k){
			continue;
		}
		pq.push(make_pair(-all[x][last[x]]-all[x][m-k+last[x]],x));
	}
	for(int i=0;i<n;i++){
		int cnt=0;
		for(int j=0;j<last[i];j++){
			res[i][j]=cnt;
			cnt++;
		}
		for(int j=last[i];j<m-k+last[i];j++){
			res[i][j]=-1;
		}
		for(int j=m-k+last[i];j<m;j++){
			res[i][j]=cnt;
			cnt++;
		}
		akh[i]=m-1;
	}
	for(int val=0;val<k;val++){
		int cnt1=0,cnt2=0;
		for(int i=0;i<n;i++){
			tof[i]=0;
			if(av[i]>=last[i]){
				cnt2++;
				res[i][akh[i]]=val;
				akh[i]--;
			}else if(akh[i]<m-k+last[i]){
				cnt1++;
				res[i][av[i]]=val;
				av[i]++;
			}else{
				tof[i]=1;
			}
		}
		for(int i=0;i<n;i++){
			if(tof[i]==1){
				if(cnt1==n/2){
					res[i][akh[i]]=val;
					akh[i]--;
					cnt2++;
				}else{
					res[i][av[i]]=val;
					av[i]++;
					cnt1++;
				}
			}
		}
	}
	allocate_tickets(res);
	return mainres;
}

• 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