Submission #1063185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063185		jamjanek	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	2270 ms	154676 KiB

tickets

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


long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	int i, j;

	vector<vector<int>>answer = x;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			answer[i][j] = -1;

	long long wynik = 0;
	priority_queue<pair<long long, pair<int, int>>>kolejka;
	vector<set<int>>dodatnie(n), ujemne(n);

	for(i=0;i<n;i++){
		for(j=m-k;j<m;j++){
			wynik+=x[i][j];
			dodatnie[i].insert(j);
		}
		kolejka.push({-(long long)x[i][m-k]-x[i][0], {i, 0}});
	}
//	int dl = m-k;
	for(int minus=0;minus<k*n/2;minus++){
		i = kolejka.top().second.first;
		j = kolejka.top().second.second;
		wynik+=kolejka.top().first;
//		printf("%d %d %d\n", i, j, wynik);
		kolejka.pop();
		ujemne[i].insert(j);
		dodatnie[i].erase(j+m-k);
		j++;
		if(j<k)
			kolejka.push({-(long long)x[i][m-k+j]-x[i][j], {i,j}});
	}
//	for(i=0;i<n;i++){
//		for(auto j: ujemne[i])printf("%d ", j);printf("\n");
//		for(auto j: dodatnie[i])printf("%d ", j);printf("\n");
//}	//exit(0);
	//0011111
	//1111100
	set<pair<int,int>>najwiecej;
	for(i=0;i<k;i++){
		najwiecej.clear();
		for(j=0;j<n;j++)najwiecej.insert({dodatnie[j].size(), j});
		
		for(int ij=0;ij<n;ij++){
			j = (*najwiecej.rbegin()).second;
			najwiecej.erase(*najwiecej.rbegin());
			if(ij<n/2){
				auto it = *dodatnie[j].begin();
				answer[j][it] = i;
				dodatnie[j].erase(it);
			}
			else{
				auto it = *ujemne[j].begin();
				answer[j][it] = i;
				ujemne[j].erase(it);
			}
		}
	}
	vector<vector<int>>res = x;
	long long w2 = 0;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++){
			if(answer[i][j]>=0)
				res[i][answer[i][j]] = x[i][j];
		}
	for(i=0;i<k;i++){
		vector<int>wiersz;
		for(j=0;j<n;j++)
			wiersz.push_back(res[j][i]);
		sort(wiersz.begin(), wiersz.end());
		for(j=0;j<n;j++)
			if(j<n/2)
				w2-=wiersz[j];
			else
				w2+=wiersz[j];
	}
//	if(w2!=wynik)printf("%d %d!!!\n", wynik, w2);
//	exit(0);
	allocate_tickets(answer);
	return wynik;
	
}

• 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