Submission #614140

#	Time	Username	Problem	Language	Result	Execution time	Memory
614140		Tigryonochekk	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	853 ms	73028 KiB

tickets

#include <iostream>
#include <algorithm>
#include "tickets.h"
#include <vector>
#include <set>
#define ll long long
using namespace std;
const ll inf = 1e18 + 69;
#define pii pair<ll, int>
const int N = 1502;

int n, m, k;
vector<vector<int>> x;
vector<vector<int>> answer;
ll ans;
set<pii> fid; // .first = sum, .second = index
pii cnt[N]; //.first = cnt, .second = index
int sig[N][N]; // +, =, -
int topj[N], botj[N];

void srt() {
	auto it = fid.end();
	it--;
	int i = (*it).second;
	fid.erase(*it);
	sig[i][botj[i]] = 0;
	botj[i]--;
	topj[i]--;
	sig[i][topj[i]] = 1;
	cnt[i].first++;
	if (botj[i] >= 0) {
		fid.insert(pii(x[i][topj[i] - 1] + x[i][botj[i]], i));
	}
}

void play(int j) {
	sort(cnt, cnt + n);
	for (int i = 0; i < n / 2; i++) {
		int ii = cnt[i].second, jj = botj[ii];
		answer[ii][jj] = j;
		botj[ii]++;
	}
	for (int i = n / 2; i < n; i++) {
		int ii = cnt[i].second, jj = topj[ii];
		answer[ii][jj] = j;
		topj[ii]--;
		cnt[i].first--;
	}
}

long long find_maximum(int klir, vector<vector<int>> xuy) {
	k = klir;
	x = xuy;
	n = x.size();
	m = x[0].size();
	answer.resize(n);
	for (int i = 0; i < n; i++) {
		answer[i].resize(m, -1);
	}

	fill(topj, topj + n, m);
	fill(botj, botj + n, k - 1);
	for (int i = 0; i < n; i++) {
		cnt[i] = pii(0, i);
		for (int j = 0; j < k; j++) {
			sig[i][j] = -1;
		}
		fid.insert(pii(x[i][topj[i] - 1] + x[i][botj[i]], i));
	}

	for (int i = 0; i < n * k / 2; i++) {
		srt();
	}

	fill(topj, topj + n, m - 1);
	fill(botj, botj + n, 0);
	for (int j = 0; j < k; j++) {
		play(j);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			ans += x[i][j] * sig[i][j];
		}
	}
	allocate_tickets(answer);
	return ans;
}
/*
2 3 2
0 2 5
1 1 3

4 2 1
5 9
1 4
3 6
2 7

2 2 2 
1 1 
1 1 
*/

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