Submission #1174181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174181		hyakup	Carnival Tickets (IOI20_tickets)	C++20	76 / 100	1612 ms	215260 KiB

tickets

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

#define ll long long

long long find_maximum(int k, vector<vector<int>> v ) {
	int n = v.size(), m = v[0].size();

	vector<set<int>> smax(n), smin(n);
	ll resp = 0;
	vector<tuple<ll, int, int, int>> ordem;
	for( int i = 0; i < n; i++ ){
		for( int j = 0; j < k; j++ ){
			ordem.emplace_back( -v[i][j] - v[i][m - k + j], i, j, m - k + j );
			smax[i].insert(m - k + j);
			resp += v[i][m - k + j];
		}
	}

	sort( ordem.rbegin(), ordem.rend() );

	for( int t = 0; t < n*k/2; t++ ){
		auto [val, i, j1, j2] = ordem[t];
		resp += val;
		smax[i].erase(j2);
		smin[i].insert(j1);
	}

	vector<vector<int>> tickets( n, vector<int>(m, -1));
	vector<int> round(n);
	iota(round.begin(), round.end(), 0);
	for( int t = 0; t < k; t++ ){
		sort( round.begin(), round.end(), [&]( int a, int b ){
			return smax[a].size() < smax[b].size();
		});

		for( int i = 0; i < n/2; i++ ){
			tickets[round[i]][*smin[round[i]].begin()] = t;
			smin[round[i]].erase(smin[round[i]].begin());
		}
		for( int i = n/2; i < n; i++ ){
			tickets[round[i]][*smax[round[i]].begin()] = t;
			smax[round[i]].erase(smax[round[i]].begin());
		}
	}
	allocate_tickets(tickets);
	return resp;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 0 / 10