Submission #824740

#	Time	Username	Problem	Language	Result	Execution time	Memory
824740		thimote75	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	686 ms	76196 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

using di = pair<int, int>;
using vd = vector<di>;

int find_maximum(signed K, vector<vector<signed>> x) {
	int N = x.size(); int M = x[0].size(); int H = N >> 1;

	int result = 0;
	for (int i = 0; i < N; i ++)
		for (int k = 1; k <= K; k ++)
			result += x[i][M - k];

	priority_queue<di> deltas;
	idata R(N, M - K);
	for (int i = 0; i < N; i ++)
		deltas.push({ - x[i][0] - x[i][M - K], i });
	
	for (int i = 0; i < H * K; i ++) {
		di curr = deltas.top(); deltas.pop();

		int j = curr.second;
		result += curr.first;
		R[j] ++;
		if (R[j] == M) continue ;

		int al = R[j] - (M - K);
		deltas.push({ - x[j][al] - x[j][R[j]], j });
	}

	vector<vector<signed>> allocations(N, vector<signed>(M, -1));

	idata L(N, 0);
	for (int k = 0; k < K; k ++) {
		vd RV;
		for (int i = 0; i < N; i ++)
			RV.push_back({ R[i], i });

		sort(RV.rbegin(), RV.rend());

		for (int i = 0; i < H; i ++) {
			int e = RV[i].second;
			allocations[e][L[e]] = k;
			L[e] ++;
		}

		for (int i = H; i < N; i ++) {
			int e = RV[i].second;
			allocations[e][R[e]] = k;
			R[e] ++;
		}
	}

	allocate_tickets(allocations);

	return result;
}

• 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