제출 #1050490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1050490		Huseyn123	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	766 ms	136836 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 res=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++){
    			res+=abs(a[i]-a[n/2]);
    		}
    		for(ll i=0;i<n;i++){
    			answer.pb({0});
    		}
    	}
    	else if(k==1){
    		for(ll i=0;i<n;i++){
    			vector<int> d;
    			for(ll j=0;j<m;j++){
    				d.pb(-1);
    			}
    			answer.pb(d);
    		}
    		res=-1;
    		ll ind=0;
    		ll l[n],f[n];
    		vector<array<ll,3>> c;
    		for(ll i=0;i<n;i++){
    			for(ll 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<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]==m-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]==0){
    				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]==m-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]==m-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][0]=0;
    					}
    				}
    				if(s1.find(p)!=s1.end()){
    					if((ll)s2.size()==0){
    						continue;
    					}
    					p=*(--s2.end());
    					answer[p.second][0]=0;
    				}
    				for(ll 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<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]==m-1){
    				answer[c[i][1]][0]=0;
    				cnt++;
    				if((ll)s1.size()>n/2-cnt){
    					pair<ll,ll> h=*(s1.begin());
    					s1.erase(h); 
    					s2.insert(h);
    				}
    			}
    		}
    	}
		else{
			for(ll i=0;i<n;i++){
    			vector<int> d;
    			for(ll j=0;j<m;j++){
    				d.pb(-1);
    			}
    			answer.pb(d);
    		}
			int cnt[n][2],ind[n][2];
			for(int i=0;i<n;i++){
				cnt[i][0]=cnt[i][1]=0; 
				ind[i][0]=0; 
				ind[i][1]=m-1;
			}
			for(int i=0;i<n;i++){
				for(int j=0;j<m;j++){
					cnt[i][x[i][j]]++;
				}
			}
			for(int i=0;i<k;i++){
				int cnt0,cnt1,h0,h1;
				cnt0=cnt1=0;
				for(int j=0;j<n;j++){
					if(cnt[j][0]>0){
						cnt0++;
					}
					if(cnt[j][1]>0){
						cnt1++;
					}
				}
				if(cnt0>=n/2 && cnt1>=n/2){
					h0=n/2;
					h1=n/2; 
					if(n%2){
						if(cnt1>cnt0){
							h1++;
						}
						else{
							h0++;
						}
					}
				}
				else if(cnt0<cnt1){
					h0=cnt0;
					h1=n-h0;
				}
				else{
					h1=cnt1;
					h0=n-h1;
				}
				res+=min(h0,h1);
				for(int j=0;j<n;j++){
					if((cnt[j][0]>0)+(cnt[j][1]>0)==1){
						if(cnt[j][0]){
							h0--;
							answer[j][ind[j][0]]=i;
							ind[j][0]++;
							cnt[j][0]--;
						}
						if(cnt[j][1]){
							h1--;
							answer[j][ind[j][1]]=i;
							ind[j][1]--;
							cnt[j][1]--;
						}
					}
				}
				for(int j=0;j<n;j++){
					if((cnt[j][0]>0)+(cnt[j][1]>0)==2){
						if(h0){
							h0--;
							answer[j][ind[j][0]]=i;
							ind[j][0]++;
							cnt[j][0]--;
						}
						else if(h1){
							h1--;
							answer[j][ind[j][1]]=i;
							ind[j][1]--;
							cnt[j][1]--;
						}
					}
				}
			}
		}
    	allocate_tickets(answer);
    	return res;
    }

• 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