Submission #1014625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014625		Unforgettablepl	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	562 ms	91008 KiB

tickets

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void allocate_tickets( std::vector<std::vector<int>> _x);

pair<ll,vector<vector<int>>> findans1(int k,vector<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 means max taken
		priority_queue<pair<ll,ll>> deltaq;
		for(int i=0;i<n;i++){
			ans-=q[i].front().first;
			deltaq.emplace(q[i].back().first+q[i].front().first,i);
		}
		for(int i=0;i<n/2;i++){
			auto [change,idx] = deltaq.top();deltaq.pop();
			ans+=change;
			status[idx]=true;
		}
		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();
			}
		}
	}
	return {ans,anss};
}
pair<ll,vector<vector<int>>> findans2(int k,vector<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<pair<ll,ll>> deltaq;
		for(int i=0;i<n;i++){
			ans+=q[i].back().first;
			deltaq.emplace(-q[i].back().first-q[i].front().first,i);
		}
		for(int i=0;i<n/2;i++){
			auto [change,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();
			}
		}
	}
	return {ans,anss};
}



long long find_maximum(int k, std::vector<std::vector<int>> x) {
	auto base = findans1(k,x);
	auto base2 = findans2(k,x);
	if(base.first>base2.first){
		allocate_tickets(base.second);
		return base.first;
	} else {
		allocate_tickets(base2.second);
		return base2.first;
	}
}

• 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