제출 #1167367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167367		gyg	카니발 티켓 (IOI20_tickets)	C++20	27 / 100	337 ms	97272 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define sig signed 
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second
#define mp make_pair
const int N = 1505, M = 1505, INF = 1e18;

int n, m, k;
arr<arr<int, M>, N> a, b;

arr<int, N> lst, mst;
void prp_cmp() {
	for (int i = 1; i <= n; i++) {
		lst[i] = INF, mst[i] = -1;
		for (int j = 1; j <= m; j++)
			if (!b[i][j]) lst[i] = min(lst[i], a[i][j]), mst[i] = max(mst[i], a[i][j]);

		// cout << i << ": " << lst[i] << " " << mst[i] << '\n';
	}
}

arr<arr<pii, N>, N> dp;
void dp_cmp() {
	dp[0].fill({-INF, -1});
	dp[0][0] = {0, -1};
	for (int i = 1; i <= n; i++) {
		for (int c = 0; c <= n / 2; c++) {
			int tk = (c == 0) ? -INF : dp[i - 1][c - 1].fir + mst[i];
			int lv = dp[i - 1][c].fir - lst[i];
			dp[i][c] = max(mp(tk, 1), mp(lv, 0));
		}
	}
}

arr<int, N> dr;
void dr_cmp() {
	int i = n, c = n / 2;
	while (i != 0) {
		dr[i] = dp[i][c].sec;
		if (dr[i] == 0) i--;
		else i--, c--;
	}
}

void upd(int x) {
	for (int i = 1; i <= n; i++) {
		int mn = -1, mx = -1;
		for (int j = 1; j <= m; j++) {
			if (b[i][j]) continue;
			if (a[i][j] == lst[i]) mn = j;
			if (a[i][j] == mst[i]) mx = j;
		}
		if (dr[i] == 0) b[i][mn] = x;
		else b[i][mx] = x; 
	}
}

// Return indices 0-indexed
int find_maximum(sig _k, vec<vec<sig>> _a) {
	n = _a.size(), m = _a[0].size(), k = _k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			a[i][j] = _a[i - 1][j - 1];

	int ans = 0;
	for (int x = 1; x <= k; x++) {
		prp_cmp();
		dp_cmp();
		dr_cmp();
		upd(x);
		ans += dp[n][n / 2].fir;
	}

	vec<vec<sig>> ass;
	for (int i = 1; i <= n; i++) {
		vec<sig> x;
		for (int j = 1; j <= m; j++) x.push_back(b[i][j] - 1);
		ass.push_back(x);
	}
	allocate_tickets(ass);
	return ans;
}

• 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