Submission #586541

#	Time	Username	Problem	Language	Result	Execution time	Memory
586541		Drew_	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	859 ms	84376 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();

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

	vector<ii> vec;
	vector<int> lt(N, 0), rt(N, K);
	for (int i = 0; i < N; ++i)
	{
		for (int j = M-K; j < M; ++j)
		{
			sum += V[i][j];
			vec.pb({-V[i][j] - V[i][j - (M-K)], i});
		}
	}
	sort(vec.rbegin(), vec.rend());

	for (int i = 0; i < N*K/2; ++i)
		sum += vec[i].f1, lt[vec[i].s2]++, rt[vec[i].s2]--;
	
	vector<vector<bool>> used(N, vector<bool>(K, false));
	for (int i = 0, ctr = 0; i < N; ++i)
	{
		for (int j = 0; j < lt[i]; ++j)
		{
			ans[i][j] = ctr; used[i][ctr] = true;
			ctr = (ctr + 1) % K;
		}
	}

	for (int i = 0; i < N; ++i)
	{
		for (int j = M - rt[i], k = 0; j < M; ++j)
		{
			while (used[i][k]) ++k;
			ans[i][j] = k++;
		}
	}

	allocate_tickets(ans);
	return sum;
}

• 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