Submission #600249

#	Time	Username	Problem	Language	Result	Execution time	Memory
600249		definitelynotmee	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	2 ms	724 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));
	for(int i = 0; i < n; i++){
		iota(all(resp[i]),0);
	}
	priority_queue<ticket> minus, plus;
	ll ans = 0;

	for(int i = 0; i < n/2; i++){
		for(int j = 0; j < m; j++){
			minus.push({x[i][j],i,j});
			ans-=x[i][j];
		}
	}
	for(int i = n/2; i < n; i++){
		for(int j = 0; j < m; j++){
			plus.push({-x[i][j],i,j});
			ans+=x[i][j];
		}
	}

	while(minus.top().val > plus.top().val*-1){
		ticket t1 = minus.top(), t2 = plus.top();
		minus.pop();
		plus.pop();
		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.push(t1);
		minus.push(t2);
	}
	allocate_tickets(resp);
	return ans;
}

• Subtask 1: 11 / 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