Submission #1271960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271960		BlockOG	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	620 ms	125156 KiB

tickets

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

// mrrrow meeow :3
// go play vivid/stasis now! https://vividstasis.gay

#define fo(i, a, b) for(auto i = (a); i < (b); i++)
#define pb push_back
#define f first
#define s second
#define be(a) a.begin(), a.end()
using namespace std;

int sum[1500], f[1500], b[1500];

long long find_maximum(int k, vector<vector<int>> d) {
	int n = d.size();
	int m = d[0].size();

	vector<pair<long long, pair<int, int>>> V;

	long long ans = 0;
	vector<vector<pair<long long, int>>> d2(n);
	fo(i, 0, n) fo(j, 0, m) d2[i].pb({d[i][j], j});

	fo(i, 0, n) {
		sort(be(d2[i]));
		fo(j, 0, k) V.pb({d2[i][m-1-j].f + d2[i][k-1-j].f, {i, j}}), ans -= d2[i][j].f;
	}
	sort(be(V), [](pair<long long, pair<int, int>> a, pair<long long, pair<int, int>> b) { return a.f != b.f ? a.f > b.f : a.s < b.s; });

	fo(i, 0, n * k / 2) ans += V[i].f, sum[V[i].s.f] = V[i].s.s + 1;

	vector<vector<int>> res(n, vector<int>(m, -1));
	fo(i, 0, k) {
		vector<pair<int, int>> v;
		fo(j, 0, n) v.pb({sum[j], j});
		sort(be(v));

		fo(j, 0, n / 2) res[v[j].s][d2[v[j].s][  f[v[j].s]  ].s] = i, f[v[j].s]++;
		fo(j, n / 2, n) res[v[j].s][d2[v[j].s][m-b[v[j].s]-1].s] = i, b[v[j].s]++, sum[v[j].s]--;
	}

	allocate_tickets(res);
	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