Submission #1015552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015552		Unforgettablepl	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	398 ms	88872 KiB

tickets

    #include <bits/stdc++.h>
    using namespace std;
     
    typedef long long ll;
     
    void allocate_tickets( std::vector<std::vector<int>> _x);
     
    long long find_maximum(int k, std::vector<std::vector<int>> x) {
    	int n = x.size();
    	int m = x[0].size();
    	vector<deque<pair<ll,ll>>> q;
    	for(auto&i:x){
    		q.emplace_back();
    		int idx = 0;
    		for(int&j:i)q.back().emplace_back(j,idx++);
    	}
    	vector<vector<int>> anss(n,vector<int>(m,-1));
    	ll ans=0;
    	for(int round=0;round<k;round++){
    		vector<bool> status(n,true); //True means max taken
    		priority_queue<tuple<ll,int,ll>> deltaq;
    		for(int i=0;i<n;i++){
    			ans+=q[i].back().first;
    			int pri = 0;
    			if(q[i].size()>1 and q[i].back().first!=q[i][q[i].size()-2].first)pri=2;
    			if(q[i].size()>1 and q[i][0].first==q[i][1].first)pri=1;
    			deltaq.emplace(-q[i].back().first-q[i].front().first,pri,i);
    		}
    		for(int i=0;i<n/2;i++){
    			auto [change,pri,idx] = deltaq.top();deltaq.pop();
    			ans+=change;
    			status[idx]=false;
    		}
    		for(int i=0;i<n;i++){
    			if(status[i]){
    				anss[i][q[i].back().second]=round;
    				q[i].pop_back();
    			} else {
    				anss[i][q[i].front().second]=round;
    				q[i].pop_front();
    			}
    		}
    	}
    	allocate_tickets(anss);
    	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