Submission #1022377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022377		Cyber_Wolf	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	897 ms	221680 KiB

tickets

// Problem: P3 - Carnival Tickets
// Contest: DMOJ - IOI '20
// URL: https://dmoj.ca/problem/ioi20p3
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#include "tickets.h"
#pragma GCC optimize("Ofast")

using namespace std;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


long long find_maximum(int k, vector<vector<int>> V)
{
	int n = V.size();
	int m = V[0].size();
	vector<vector<array<lg, 2>>> v;
	lg ans = 0;
	vector<array<lg, 4>> o;
	auto a = V;
	for(int i = 0; i < n; i++)
	{
		v.push_back({});
		for(int j = 0; j < m; j++)
		{
			v[i].push_back({V[i][j], j});
			a[i][j] = -1;
		}
	}
	vector<int> neg[n], pos[n];
	for(int i = 0; i < n; i++)
	{
		sort(v[i].begin(), v[i].end());
		for(int j = 0; j < k; j++)
		{
			ans -= v[i][j][0];
			o.push_back({v[i][m-k+j][0]+v[i][j][0], i, v[i][j][1], v[i][m-k+j][1]});
		}
	}
	vector<array<int, 2>> npos(n);
	for(int i = 0; i < n; i++)	npos[i] = {0, i};
	sort(o.rbegin(), o.rend());
	for(int i = 0; i < n*k/2; i++)
	{
		ans += o[i][0];
		pos[o[i][1]].push_back(o[i][3]);
		npos[o[i][1]][0]++;
	}
	for(int i = n*k/2; i < n*k; i++)
	{
		neg[o[i][1]].push_back(o[i][2]);
	}
	for(int i = 0; i < k; i++)
	{
		sort(npos.begin(), npos.end());
		//negatives
		for(int j = 0; j < n/2; j++)
		{
			a[npos[j][1]][neg[npos[j][1]].back()] = i;
			neg[npos[j][1]].pop_back();	
		}
		//positives
		for(int j = n/2; j < n; j++)
		{
			a[npos[j][1]][pos[npos[j][1]].back()] = i;
			pos[npos[j][1]].pop_back();	
			npos[j][0]--;
		}
	}
	allocate_tickets(a);
	return ans;
}

• 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