Submission #1188340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188340		esomer	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	323 ms	51372 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m, k;
set<pair<int, int>> add0, add1;

void Add0(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){
	if(zeros[i] < k) add0.insert({x[i][zeros[i]] + x[i][m-ones[i]], i});
}

void Add1(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){
	if(zeros[i] > 0) add1.insert({x[i][zeros[i]-1] + x[i][m-ones[i]-1], i});
}

void Erase0(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){
	if(zeros[i] < k) add0.erase({x[i][zeros[i]] + x[i][m-ones[i]], i});
}

void Erase1(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){
	if(zeros[i] > 0) add1.erase({x[i][zeros[i]-1] + x[i][m-ones[i]-1], i});
}

long long find_maximum(int _k, vector<vector<int>> x) {
	k = _k;
	n = (int)x.size();
	m = (int)x[0].size();
	vector<vector<int>> ans(n, vector<int>(m, -1));
	vector<pair<int, int>> rng(n, {0, m-1});
	long long res = 0;
	for(int r = 0; r < k; r++){
		vector<pair<long long, int>> difs;
		for (int i = 0; i < n; i++) {
			difs.push_back({x[i][rng[i].second] + x[i][rng[i].first], i});
		}
		sort(difs.begin(), difs.end());
		for (int j = 0; j < n/2; j++) {
			int i = difs[j].second;
			//These substract.
			res -= x[i][rng[i].first];
			ans[i][rng[i].first] = r;
			rng[i].first++;
		}
		for (int j = n/2; j < n; j++) {
			int i = difs[j].second;
			//These add.
			res += x[i][rng[i].second];
			ans[i][rng[i].second] = r;
			rng[i].second--;
		}
	}
	allocate_tickets(ans);
	return res;
}

• 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