Submission #787084

#	Time	Username	Problem	Language	Result	Execution time	Memory
787084		Pablo_No	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	351 ms	51832 KiB

tickets

#include "tickets.h"
#include <vector>
#include <queue>
#include <set>
	
using namespace std;
	
#define int long long
	
long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
	int n = x.size();
	int m = x[0].size();
	
	std::vector<std::vector<signed>> ans(n, vector<signed>(m, -1));
	long long ansv = 0;

	priority_queue<pair<int, pair<int, int>>> pq;

	set<pair<int, int>> anss, anss2;
	
	for(int j = 0; j < n; j++)
	{
		for(int i = 0; i < k; i++)
		{
			ansv += x[j][m-1-i];
			anss.insert({m-1-i, -j});
		}

		pq.push({-x[j][0]-x[j][m-k], {j, 0}});
	}

	int ac = k*n/2;

	while(ac--)
	{
		auto ss = pq.top();
		pq.pop();

		anss2.insert({ss.second.second, ss.second.first});
		anss.erase({m-k+ss.second.second, -ss.second.first});

		ansv += ss.first;

		if(ss.second.second < k-1)
			pq.push({-x[ss.second.first][ss.second.second+1]-x[ss.second.first][m-k+(ss.second.second+1)], {ss.second.first, ss.second.second+1}});
	}

	int tim = 0;

	for(auto vv : anss)
	{
		ans[-vv.second][vv.first] = tim/(n/2);
		tim++;
	}

	tim = 0;

	for(auto vv : anss2)
	{
		ans[vv.second][vv.first] = tim/(n/2);
		tim++;
	}

	
	allocate_tickets(ans);
	return ansv;
}

• 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