Submission #434592

#	Time	Username	Problem	Language	Result	Execution time	Memory
434592		frodakcin	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	619 ms	73136 KiB

tickets

#include "tickets.h"
#include <vector>
#include <numeric>
#include <algorithm>

using ll = long long;

long long find_maximum(int K, std::vector<std::vector<int>> x) {
	int N = x.size();
	int M = x[0].size();
	std::vector<std::vector<int>> answer(N, std::vector<int>(M, -1));
	ll ans=0;
	std::vector<int> L(N, 0), R(N, M);

	std::vector<int> ord(N), gain(N);
	std::iota(ord.begin(), ord.end(), 0);
	for(int i=0;i<K;++i)
	{
		for(int j=0;j<N;++j)
			gain[j]=x[j][L[j]]+x[j][R[j]-1];
		std::nth_element(ord.begin(), ord.begin()+N/2, ord.end(), [&](int u, int v){return gain[u]<gain[v];});

		for(int j=0;j<N/2;++j)
			answer[ord[j]][L[ord[j]]]=i, ans -= x[ord[j]][L[ord[j]]], ++L[ord[j]];
		for(int j=N/2;j<N;++j)
			--R[ord[j]], answer[ord[j]][R[ord[j]]]=i, ans += x[ord[j]][R[ord[j]]];
	}
	allocate_tickets(answer);
	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