Submission #600253

#	Time	Username	Problem	Language	Result	Execution time	Memory
600253		definitelynotmee	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	0 ms	212 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix= vector<vector<T>>;

struct ticket{
	int val, id, col;
	bool operator<(ticket b) const{
		return val < b.val;
	}
};

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	matrix<int> resp(n,vector<int>(m,-1));
	for(int i = 0; i < n; i++){
		iota(resp[i].begin(),resp[i].begin()+k,0);
	}
	multiset<ticket> minus, plus;
	ll ans = 0;

	for(int i = 0; i < n/2; i++){
		for(int j = 0; j < k; j++){
			minus.insert({-x[i][j],i,j});
			ans-=x[i][j];
		}
	}
	for(int i = n/2; i < n; i++){
		for(int j = 0; j < k; j++){
			plus.insert({x[i][j],i,j});
			ans+=x[i][j];
		}
	}
	vector<int> o(n);
	iota(all(o),0);
	sort(all(o),[&](int a, int b){
		return resp[a][0]+resp[a][1] > resp[b][0]+resp[b][1];
	});
	while(minus.begin()->val > plus.begin()->val*-1){
		ticket t1 = *minus.begin(), t2 = *plus.begin();
		minus.erase(minus.begin());
		plus.erase(plus.begin());
		swap(resp[t1.id][t1.col],resp[t2.id][t2.col]);
		ans+=t1.val*-2;
		ans+=t2.val*-2;
		t1.val*=-1;
		t2.val*=-1;
		plus.insert(t1);
		minus.insert(t2);
	}
	allocate_tickets(resp);
	return ans;
}

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