제출 #1050423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1050423		Huseyn123	카니발 티켓 (IOI20_tickets)	C++17	27 / 100	3051 ms	127148 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) {
	ll n = x.size();
	ll m = x[0].size();
	vector<vector<int>> answer;
	ll ans=0;
	if(m==1){
		vector<ll> a; 
		for(ll i=0;i<n;i++){
			a.pb(x[i][0]);
		}
		sort(a.begin(),a.end());
		for(ll i=0;i<n;i++){
			ans+=abs(a[i]-a[n/2]);
		}
		for(ll i=0;i<n;i++){
			answer.pb({0});
		}
	}
	else{
		for(ll i=0;i<n;i++){
			vector<int> d;
			for(ll j=0;j<m;j++){
				d.pb(-1);
			}
			answer.pb(d);
		}
		for(int z=0;z<k;z++){
			ll res=-1;
			ll ind=0;
			ll l[n],f[n],l1[n],f1[n];
			vector<array<ll,3>> c;
			for(ll i=0;i<n;i++){
				for(ll j=0;j<m;j++){
					if(answer[i][j]==-1){
						c.pb({x[i][j],i,j});
						l[i]=x[i][j];
						l1[i]=j;
					}
				}
				for(ll j=m-1;j>=0;j--){
					if(answer[i][j]==-1){
						f[i]=x[i][j];
						f1[i]=j;
					}
				}
			}
			sort(c.begin(),c.end()); 
			set<pair<ll,ll>> s1,s2;
			ll cnt=0; 
			ll sum1=0,sum2=0,sum3=0;
			ll sz=(ll)c.size();
			for(ll i=0;i<n;i++){
				sum3+=l[i];
			}
			for(ll i=0;i<sz;i++){
				if(n/2-cnt<0){			
					break;
				}
				if(c[i][2]==l1[c[i][1]]){
					pair<ll,ll> 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((ll)s1.size()==n/2-cnt){
					ll sum=sum2;
					pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
					if(s1.find(p)!=s1.end()){
						if((ll)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]==f1[c[i][1]]){
					pair<ll,ll> p=*(s1.begin());
					pair<ll,ll> nw={-l[c[i][1]]-f[c[i][1]],c[i][1]};
					if((ll)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]==l1[c[i][1]]){
					cnt++;
					sum1+=f[c[i][1]];
					if((ll)s1.size()>n/2-cnt){
						pair<ll,ll> 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(ll i=0;i<=ind;i++){
				if(n/2-cnt<0){			
					break;
				}
				if(c[i][2]==l1[c[i][1]]){
					pair<ll,ll> 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<ll,ll> 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][f1[x.second]]=z;
						}
					}
					if(s1.find(p)!=s1.end()){
						if((ll)s2.size()==0){
							continue;
						}
						p=*(--s2.end());
						answer[p.second][f1[p.second]]=z;
					}
					for(ll j=0;j<n;j++){
						if(j==c[i][1]){
							answer[c[i][1]][c[i][2]]=z;
							continue;
						}
						if(answer[j][f1[j]]==-1 && answer[j][l1[j]]==-1){
							answer[j][l1[j]]=z;
						}
					}
					break;
				}
				if(c[i][2]==f1[c[i][1]]){
					pair<ll,ll> p=*(s1.begin());
					pair<ll,ll> nw={-l[c[i][1]]-f[c[i][1]],c[i][1]};
					if((ll)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]==l1[c[i][1]]){
					answer[c[i][1]][f1[c[i][1]]]=z;
					cnt++;
					if((ll)s1.size()>n/2-cnt){
						pair<ll,ll> h=*(s1.begin());
						s1.erase(h); 
						s2.insert(h);
					}
				}
			}
			ans+=res;
		}
	}
	ans=0;
	for(int z=0;z<k;z++){
		vector<ll> a; 
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(answer[i][j]==z){
					a.pb(x[i][j]);
				}
			}
		}
		sort(a.begin(),a.end());
		for(ll i=0;i<n;i++){
			ans+=abs(a[i]-a[n/2]);
		}
	}
	allocate_tickets(answer);
	return ans;
}

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