Submission #565817

#	Time	Username	Problem	Language	Result	Execution time	Memory
565817		sidon	Carnival Tickets (IOI20_tickets)	C++17	41 / 100	803 ms	98204 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 {};

	if(k < 2) {
		array<ll, 2> a[n] {};
		for(int i = n; i--; ) {
			res -= x[i][0];
			a[i] = {x[i][0] + x[i][m-1], i};
		}
		sort(a, a + n);
		for(int i = n/2; i < n; ++i)
			g[a[i][1]][m-1] = 0, res += a[i][0];
		for(int i = n/2; i--; )
			g[a[i][1]][0] = 0;
	} else if(k == m) {
		vector<array<int, 3>> a;
		for(int i = n; i--; )
			for(int j = m; j--; )
				a.push_back({x[i][j], i, j});
		sort(begin(a), end(a));

		for(int i = size(a); --i >= (k * n / 2); )
			++g[a[i][1]][a[i][2]];

		for(int i = n; i--; ) for(int j = m; j--; )
			res += (g[i][j] ? : 1) * x[i][j];

		int l[n] {}, r[n];
		bool vis[n];
		fill(r, r + n, m-1);

		for(int c = 0; c < k; ++c) {
			int cnt {};
			fill(vis, vis + n, 0);
			for(int i = n; i--; ) {
				if(!g[i][l[i]])
					g[i][l[i]++] = c, ++cnt, vis[i] = 1;
				if(g[i][r[i]])
					g[i][r[i]--] = c, --cnt, vis[i] = 1;
			}
			for(int i = n; i--; ) if(!vis[i]) {
				if(cnt < 0)
					g[i][r[i]--] = c, ++cnt;
				else
					g[i][l[i]++] = c, --cnt;
			}
		}
	} else assert(0);

	allocate_tickets(g);
	return res;
}

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