Submission #1062846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062846		jamjanek	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	2203 ms	2097152 KiB

tickets

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

void usun(vector<int>&ile, set<pair<int, int>>&ilejedynek, int x){
	pair<int,int> it = {ile[x], x};
	ilejedynek.erase(it);
	ile[it.second]--;
	ilejedynek.insert({it.first-1, it.second});
	
}

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	int i, j;
	set<pair<int,int>>ilejedynek;
	vector<int>ile;
	for(i=0;i<n;i++){
		int suma = 0;
		for(j=0;j<m;j++)
			suma+=x[i][j];
		ilejedynek.insert({suma, i});
		ile.push_back(suma);
	}
//	for(i=0;i<n;i++)printf("%d ", ile[i]);
	
	vector<std::vector<int>> answer(n);
	int r = m;
	int wynik=0;
	for(int i=0;i<k;i++){
		int pom = 0;
		for(j=0;j<n/2;j++)
			if((*ilejedynek.rbegin()).first>0){
				auto it = *ilejedynek.rbegin();
				answer[it.second].push_back(1);
				usun(ile, ilejedynek, it.second);
				pom++;
			}
		for(j=0;j<n;j++)
			if((int)answer[j].size()<=i){
				if(ile[j]==r){
					answer[j].push_back(1);
					usun(ile, ilejedynek, j);
					pom++;
				}
				else{
					answer[j].push_back(0);
				}
			}
		wynik+=min(pom, n-pom);
		r--;
	}
//	for(i=0;i<n;i++)printf("%d ", ile[i]);
	for(i=0;i<n;i++){
		while(ile[i]){
			answer[i].push_back(1);
			ile[i]--;
		}
		while((int)answer[i].size()<m)
			answer[i].push_back(0);
	}
//	for(i=0;i<n;i++)printf("%d ", answer[i].size());
	allocate_tickets(answer);
	return wynik;
}

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