Submission #565857

#	Time	Username	Problem	Language	Result	Execution time	Memory
565857		sidon	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	498 ms	51420 KiB

tickets

#include "tickets.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size(), m = x[0].size();
	vector<vector<int>> g(n, vector<int> (m, -1));
	ll res {};
	int l[n] {}, r[n];
	fill(r, r + n, m-1);

	for(int c = 0; c < k; ++c) {
		array<ll, 2> a[n] {};
		for(int i = n; i--; ) {
			res -= x[i][l[i]];
			a[i] = {x[i][l[i]] + x[i][r[i]], i};
		}
		sort(a, a + n);
		for(int i = n/2; i < n; ++i)
			g[a[i][1]][r[a[i][1]]--] = c, res += a[i][0];
		for(int i = n/2; i--; )
			g[a[i][1]][l[a[i][1]]++] = c;
	}

	allocate_tickets(g);
	return res;
}

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