Submission #316142

#	Time	Username	Problem	Language	Result	Execution time	Memory
316142		srvlt	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	2 ms	768 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) (int)(x).size()
#define all(x) begin(x), end(x)
using namespace std;

ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> ans;
	for (int i = 0; i < n; i++)
		ans.push_back(vector <int>(m, -1));
	vector <int> l(n, 0), r(n, m - 1), used(n);
	set <array <int, 3>> st;
	ll res = 0;
	for (int s = 0; s < k; s++) {
		st.clear();
		for (int & i : used) i = 0;
		for (int i = 0; i < n; i++) {
			if (l[i] > r[i]) continue;
			st.insert({x[i][l[i]], i, 0});
			if (l[i] != r[i])
				st.insert({x[i][r[i]], i, 1});
		}
		while (SZ(st) >= 2) {
			auto a = *begin(st);
			auto b = *prev(end(st));
			if (used[a[1]]) {
				st.erase(begin(st)); continue;
			}
			if (used[b[1]]) {
				st.erase(prev(end(st))); continue;
			}
			if (a[1] == b[1]) {
				assert(SZ(st) > 2);
				auto a2 = *next(begin(st));
				auto b2 = *prev(prev(end(st)));
				int x = b2[0] - a[0];
				int y = b[0] - a2[0];
				if (x > y) {
					res += x;
					if (b2[2] == 0) ans[b2[1]][l[b2[1]]++] = s;
					else ans[b2[1]][r[b2[1]]--] = s;
					if (a[2] == 0) ans[a[1]][l[a[1]]++] = s;
					else ans[a[1]][r[a[1]]--] = s;
					st.erase(begin(st)), st.erase(prev(prev(end(st))));
					used[a[1]] = used[b2[1]] = 1;
				}	else {
					res += y;
					if (b[2] == 0) ans[b[1]][l[b[1]]++] = s;
					else ans[b[1]][r[b[1]]--] = s;
					if (a2[2] == 0) ans[a2[1]][l[a2[1]]++] = s;
					else ans[a2[1]][r[a2[1]]--] = s;
					st.erase(next(begin(st))), st.erase(prev(end(st)));
					used[a2[1]] = used[b[1]] = 1;
				}
			}	else {
				res += b[0] - a[0];
				if (a[2] == 0) ans[a[1]][l[a[1]]++] = s;
				else ans[a[1]][r[a[1]]--] = s;
		
				if (b[2] == 0) ans[b[1]][l[b[1]]++] = s;
				else ans[b[1]][r[b[1]]--] = s;
				used[a[1]] = used[b[1]] = 1;
				st.erase(begin(st)), st.erase(prev(end(st)));
			}
		}
	}
	allocate_tickets(ans);
	return res;
}

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