Submission #823648

#	Time	Username	Problem	Language	Result	Execution time	Memory
823648		GusterGoose27	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	589 ms	65388 KiB

tickets

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

using namespace std;

typedef long long ll;

const int MAXN = 1505;
int pos[MAXN];
int n, m, k;
vector<vector<int>> x;
int alloc[2];
int apos[2];

typedef pair<int, int> pii;

int get_val(int i) {
	return x[i][k-pos[i]-1]+x[i][m-pos[i]-1];
}

bool mat[MAXN][MAXN];
int cap[MAXN];
int match[2][MAXN];

// bool flow(int cur, bool side = 0) {
// 	if (side && cap[cur]) {
// 		cap[cur]--;
// 		return 1;
// 	}
// 	if (side == 0) {
// 		for (; match[0][cur] < k; match[0][cur]++) {
// 			if (!mat[cur][match[0][cur]]) continue;
// 			bool b = flow(match[0][cur], 1);
// 			if (b) {
// 				mat[cur][match[0][cur]] ^= 1;
// 				return 1;
// 			}
// 		}
// 		return 0;
// 	}
// 	if (side == 1) {
// 		for (; match[1][cur] < n; match[1][cur]++) {
// 			if (mat[match[1][cur]][cur]) continue;
// 			bool b = flow(match[1][cur], 0);
// 			if (b) {
// 				mat[match[1][cur]][cur] ^= 1;
// 				return 1;
// 			}
// 		}
// 		return 0;
// 	}
// 	assert(false);
// }

ll find_maximum(int K, vector<vector<int>> X) {
	k = K;
	x = X;
	ll ans = 0;
	n = x.size();
	m = x[0].size();
	priority_queue<pii> pq;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			ans -= x[i][j];
		}
		pq.push(pii(get_val(i), i));
	}
	for (int _ = 0; _ < n*k/2; _++) {
		pii tp = pq.top(); pq.pop();
		ans += tp.first;
		pos[tp.second]++;
		if (pos[tp.second] < k) pq.push(pii(get_val(tp.second), tp.second));
	}
	fill(cap, cap+k, n/2);
	// for (int i = 0; i < n; i++) fill(mat[i], mat[i]+k, 1);
	int p = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < pos[i]; j++) {
			mat[i][p++] = 1;
			p %= k;
			// bool b = flow(i);
			// if (!b) exit(0);
			// assert(b);
		}
	}
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row(m, -1);
		int a = 0, b = m-pos[i];
		for (int j = 0; j < k; j++) {
			if (!mat[i][j]) {
				assert(a < k-pos[i]);
				row[a++] = j;
			}
			else {
				assert(b < m);
				row[b++] = j;
			}
		}
		answer.push_back(row);
	}
	allocate_tickets(answer);
	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