Submission #1232342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232342		M_W_13	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	681 ms	83916 KiB

tickets

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	int dod[n];
	int uj[n];
	int ile[n];
	int gora[n];
	int dol[n];
	rep(i, n) {
		ile[i] = 0;
		dod[i] = 0;
		dol[i] = 0;
		gora[i] = m - 1;
		uj[i] = k;
	}
	priority_queue<pair<ll, int>> pq;
	ll ans = 0;
	rep(i, n) {
		rep(j, k) {
			ans -= x[i][j];
		}
	}
	rep(i, n) {
		rep(j, k) {
			pq.push({x[i][m - 1 - j] + x[i][k - 1 - j], i});
		}
	}
	ll pom = (k * n)/2;
	while (pom--) {
		pair<ll, int> p = pq.top();
		pq.pop();
		if (ile[p.nd] == k) continue;
		ile[p.nd]++;
		dod[p.nd]++;
		uj[p.nd]--;
		ans += p.st;
	}
	vector<vector<int>> s;
	rep(i, n) {
		s.pb({});
		rep(j, m) {
			s[i].pb(-1);
		}
	}
	rep(r, k) {
		vector<pair<int, int>> vec;
		rep(i, n) {
			vec.pb({uj[i], i});
		}
		sort(vec.begin(), vec.end());
		int n2 = n/2;
		rep(i, n2) {
			int it = vec[i].nd;
			s[it][gora[it]] = r;
			dod[it]--;
			gora[it]--;
		}
		for (int i = n2; i < n; i++) {
			int it = vec[i].nd;
			s[it][dol[it]] = r;
			uj[it]--;
			dol[it]++;
		}
	}
	allocate_tickets(s);
	return ans;
}

• 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