Submission #459482

#	Time	Username	Problem	Language	Result	Execution time	Memory
459482		astoria	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1136 ms	100076 KiB

tickets

    #include "bits/stdc++.h"
	#include "tickets.h"
    using namespace std;
    typedef long long ll;
     
    long long find_maximum(int k, std::vector<std::vector<int>> x) {
    	int N=x.size(), M=x[0].size();
    	
    	vector<vector<int> > ans(N);
    	for(int i=0; i<N; i++) ans[i].resize(M);
    	
    	for(int i=0; i<N; i++)
    		for(int j=0; j<M; j++)
    			ans[i][j] = -1;
    	
    	ll sum=0;
    	
    	priority_queue<pair<ll,pair<int,int> > > pq; //<value, <colour,ticket> >
    	
    	for(int i=0; i<N; i++){
    		for(int j=0; j<k; j++){
    			sum -= x[i][j];
    			pq.push({x[i][j]+x[i][M-k+j] , {i,j} });
    			ans[i][j] = 0; //'-'
    		}
    	}
    	
    	int trades = N*k/2;
    	for(int ahc=0; ahc<trades; ahc++){
    		ll v = pq.top().first; int i=pq.top().second.first, j=pq.top().second.second;
    		pq.pop();
    		ans[i][j]=-1; ans[i][M-k+j] = 1; //'+'
    		sum += v;
    	}
    	int l[2000],r[2000]; pair<int,int> arr[2000];
    	for(int i=0; i<N; i++){
    		for(int j=0; j<M; j++){
    			if (ans[i][j]==1){ r[i]=M-1; arr[i].first++;}
    			else if (ans[i][j]==0) l[i]=0;
    		}
    		arr[i].second = i;
    	}
    	
    	for (int i=0; i<k; i++) {
    		sort(arr, arr+N);
    		for (int j=0; j<N; j++) {
    			int id=arr[j].second;
    			if (j<N/2) ans[id][l[id]++]=i;
    			else ans[id][r[id]--]=i, arr[j].first--;
    		}
    	}
    	allocate_tickets(ans);
    	return sum;
    }

• 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