제출 #823636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823636		GusterGoose27	카니발 티켓 (IOI20_tickets)	C++17	76 / 100	517 ms	65324 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);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < pos[i]; j++) {
			bool b = flow(i);
			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;
			}
		}
		// for (int j = 0; j < k-pos[i]; j++) {
		// 	row[j] = apos[0];
		// 	alloc[0]++;
		// 	if (alloc[0] == n/2) {
		// 		alloc[0] = 0;
		// 		apos[0]++;
		// 	}
		// }
		// for (int j = m-pos[i]; j < m; j++) {
		// 	row[j] = apos[1];
		// 	alloc[1]++;
		// 	if (alloc[1] == n/2) {
		// 		alloc[1] = 0;
		// 		apos[1]++;
		// 	}
		// }
		answer.push_back(row);
	}
	allocate_tickets(answer);
	return ans;
}

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