Submission #585930

#	Time	Username	Problem	Language	Result	Execution time	Memory
585930		Drew_	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	1378 ms	90852 KiB

tickets

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

#define pb push_back
#define f1 first
#define s2 second

using ii = pair<int, int>;
using ll = long long;

ll find_maximum(int K, vector<vector<int>> V)
{
	int N = (int)V.size(), M = (int)V[0].size();
	
	vector<vector<ii>> vec(N, vector<ii>(M));
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			vec[i][j] = {V[i][j], j};

	for (int i = 0; i < N; ++i)
		sort(vec[i].begin(), vec[i].end());

	ll S = 0;
	vector<vector<int>> ans(N, vector<int> (M, -1));

	priority_queue<ii> pq;
	vector<bool> used(N, false);
	for (int i = 0; i < K; ++i)
	{
		while (!pq.empty())
			pq.pop();

		if (i+1 == M)
		{
			ll sum = 0;
			for (int j = 0; j < N; ++j)
			{
				sum += vec[j][0].f1;
				pq.push({-2*vec[j][0].f1, 69});
				
				ans[j][vec[j][0].s2] = i;
			}

			for (int j = 0; j < N/2; ++j)
				sum += pq.top().f1, pq.pop();
			
			S += sum;
		}
		else
		{
			fill(used.begin(), used.end(), false);

			ll sum = 0;
			for (int j = 0; j < N; ++j)
			{
				sum += vec[j].back().f1;
				pq.push({-vec[j][0].f1 - vec[j].back().f1, j});
			}

			for (int j = 0; j < N/2; ++j)
			{
				sum += pq.top().f1;
				used[pq.top().s2] = true;
				
				pq.pop();
			}

			for (int j = 0; j < N; ++j)
			{
				if (used[j])
				{
					ans[j][vec[j][0].s2] = i;
					vec[j].erase(vec[j].begin());
				}
				else
				{
					ans[j][vec[j].back().s2] = i;
					vec[j].pop_back();
				}
			}

			S += sum;
		}
	}

	allocate_tickets(ans);
	return S;
}

• 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