Submission #1170573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170573		gyg	카니발 티켓 (IOI20_tickets)	C++20	100 / 100	592 ms	89632 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; // sorted in input 

arr<int, N> blc;
void blc_cmp() {
	blc.fill(k);
	set<pii> ord;
	for (int i = 1; i <= n; i++) 
		ord.insert({a[i][blc[i]] + a[i][m - k + blc[i]], i});
	
	for (int x = 1; x <= n * k / 2; x++) {
		int i = ord.rbegin()->sec;
		ord.erase(--ord.end());
		blc[i]--;
		if (blc[i] == 0) continue;
		ord.insert({a[i][blc[i]] + a[i][m - k + blc[i]], i});
	}

	// for (int i = 1; i <= n; i++) 
	// 	cout << i << ": " << blc[i] << '\n';
}

arr<arr<int, M>, N> ass;
int ass_cmp() {
	int ans = 0;
	for (int x = 1; x <= k; x++) {
		int y = k - x + 1;
		vec<pii> ord;
		for (int i = 1; i <= n; i++) 
			ord.push_back({y - blc[i], i});
		sort(ord.rbegin(), ord.rend());

		for (int j = 0; j < n; j++) {
			int i = ord[j].sec;
			if (j <= n / 2 - 1) {
				ass[i][m - y + blc[i] + 1] = x;
				ans += a[i][m - y + blc[i] + 1];
			} else {
				ass[i][blc[i]] = x;
				ans -= a[i][blc[i]];
				blc[i]--;
			}
		}
	}
	return ans;
}

// 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];			

	blc_cmp();

	int ans = ass_cmp();

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

	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