Submission #489728

#	Time	Username	Problem	Language	Result	Execution time	Memory
489728		8e7	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	627 ms	93880 KiB

tickets

#include "tickets.h"
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <random>
#include <chrono>
#include <queue>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 1505
#define pii pair<int, int>
#define ff first
#define ss second
const ll inf = 1LL<<60;
ll cost[maxn][maxn];
int pref[maxn], suf[maxn];
priority_queue<pii, vector<pii>, less<pii> > pq;
long long find_maximum(int k, vector<vector<int> > x) {
	int n = x.size();
	int m = x[0].size();
	ll tot = 0, small = 0;
	for (int i = 0;i < n;i++) {
		for (int j = m - k;j < m;j++) {
			tot += x[i][j];
			cost[i][j - m + k] = -x[i][j - m + k] - x[i][j];
		}	
		//pary(cost[i], cost[i] + k + 1);
	}
	vector<vector<int> > ans(n, vector<int>(m, -1));
	for (int i = 0;i < n;i++) {
		pref[i] = 0, suf[i] = m - k;
		pq.push({cost[i][0], i});
	}
	for (int ti = 0;ti < n * k / 2;ti++) {
		pii best = pq.top();pq.pop();
		int i = best.ss;
		pref[i]++, suf[i]++;
		small += best.ff;
		if (pref[i] < k) pq.push({cost[i][pref[i]], i});
	}
	
	int ord[n];
	for (int i = 0;i < n;i++) ord[i] = i;
	for (int ti = 0;ti < k;ti++) {
		sort(ord, ord + n, [&](int x, int y){return pref[x] > pref[y];});
		int rem = n / 2;
		for (int j = 0;j < n;j++) {
			int i = ord[j];
			if (pref[i] && rem) {
				rem--;
				pref[i]--;
				ans[i][pref[i]] = ti;
			} else {
				ans[i][suf[i]] = ti;
				suf[i]++;
			}
		}
	}	
	allocate_tickets(ans);
	return tot + small;
}
/*
2 3 2
0 2 5
1 1 3


4 2 1
5 9
1 4
3 6
2 7
*/

• 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