Submission #1050288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050288		Huseyn123	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	1 ms	604 KiB

tickets

#include <bits/stdc++.h> 
#include "tickets.h"
#include <vector>
#define pb push_back
using namespace std; 
typedef long long ll; 
ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer;
	ll res=0;
	if(m==1){
		vector<int> a; 
		for(int i=0;i<n;i++){
			a.pb(x[i][0]);
		}
		sort(a.begin(),a.end());
		for(int i=0;i<n;i++){
			res+=abs(a[i]-a[n/2]);
		}
		for(int i=0;i<n;i++){
			answer.pb({0});
		}
	}
	else if(k==1){
		for(int i=0;i<n;i++){
			vector<int> d;
			for(int j=0;j<m;j++){
				d.pb(-1);
			}
			answer.pb(d);
		}
		res=-1;
		int ind=0;
		int l[n],f[n];
		vector<array<int,3>> c;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				c.pb({x[i][j],i,j});
			}
			l[i]=x[i][m-1]; 
			f[i]=x[i][0];
		}
		sort(c.begin(),c.end()); 
		set<pair<int,int>> s1,s2;
		int cnt=0; 
		ll sum1=0,sum2=0,sum3=0;
		int sz=(int)c.size();
		for(int i=0;i<n;i++){
			sum3+=l[i];
		}
		for(int i=0;i<sz;i++){
			if(n/2-cnt<0){			
				break;
			}
			if(c[i][2]==m-1){
				pair<int,int> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
				if(s1.find(p)!=s1.end()){
					s1.erase(p);
					sum2-=p.first;
				}
				else{
					s2.erase(p);
				}
			}
			ll res1=0;
			if((int)s1.size()==n/2-cnt){
				ll sum=sum2;
				pair<int,int> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
				if(s1.find(p)!=s1.end()){
					if((int)s2.size()!=0){
						sum-=p.first; 
						p=*(--s2.end());
						sum+=p.first;
						sum3-=l[c[i][1]];
						res1=sum3-(n-cnt-1)*c[i][0]+2*c[i][0]*(n/2-cnt)+sum+cnt*c[i][0]-sum1; 
						sum3+=l[c[i][1]];
					}
				}
				else{
					sum3-=l[c[i][1]];
					res1=sum3-(n-cnt-1)*c[i][0]+2*c[i][0]*(n/2-cnt)+sum+cnt*c[i][0]-sum1; 
					sum3+=l[c[i][1]];
				}
			}
			if(c[i][2]==0){
				pair<int,int> p=*(s1.begin());
				pair<int,int> nw={-l[c[i][1]]-f[c[i][1]],c[i][1]};
				if((int)s1.size()<n/2-cnt){
					s1.insert(nw);
					sum2+=nw.first;
				}
				else{
				if(nw.first>p.first){
					s1.erase(p);
					s1.insert(nw); 
					s2.insert(p);
					sum2-=p.first; 
					sum2+=nw.first;
				}
				else{
					s2.insert(nw);
				}
				}
			}
			if(c[i][2]==m-1){
				cnt++;
				sum1+=f[c[i][1]];
				if((int)s1.size()>n/2-cnt){
					pair<int,int> h=*(s1.begin());
					s1.erase(h); 
					s2.insert(h);
					sum2-=h.first;
				}
				sum3-=l[c[i][1]];
			}
			if(res1>res){
				res=res1;
				ind=i;
			}
		}
		cnt=0;
		s1.clear();
		s2.clear();
		for(int i=0;i<=ind;i++){
			if(n/2-cnt<0){			
				break;
			}
			if(c[i][2]==m-1){
				pair<int,int> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
				if(s1.find(p)!=s1.end()){
					s1.erase(p);
				}
				else{
					s2.erase(p);
				}
			}
			if(i==ind){
				pair<int,int> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
				for(auto x:s1){
					if(x.second!=c[i][1]){
						answer[x.second][0]=0;
					}
				}
				if(s1.find(p)!=s1.end()){
					if((int)s2.size()==0){
						continue;
					}
					p=*(--s2.end());
					answer[p.second][0]=0;
				}
				for(int j=0;j<n;j++){
					if(j==c[i][1]){
						answer[c[i][1]][c[i][2]]=0;
						continue;
					}
					if(answer[j][0]==-1 && answer[j][m-1]==-1){
						answer[j][m-1]=0;
					}
				}
				break;
			}
			if(c[i][2]==0){
				pair<int,int> p=*(s1.begin());
				pair<int,int> nw={-l[c[i][1]]-f[c[i][1]],c[i][1]};
				if((int)s1.size()<n/2-cnt){
					s1.insert(nw);
				}
				else{
				if(nw.first>p.first){
					s1.erase(p);
					s1.insert(nw); 
					s2.insert(p);
				}
				else{
					s2.insert(nw);
				}
				}
			}
			if(c[i][2]==m-1){
				answer[c[i][1]][0]=0;
				cnt++;
				if((int)s1.size()>n/2-cnt){
					pair<int,int> h=*(s1.begin());
					s1.erase(h); 
					s2.insert(h);
				}
			}
		}
	}
	allocate_tickets(answer);
	return res;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10