Submission #300381

#	Time	Username	Problem	Language	Result	Execution time	Memory
300381		oolimry	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1139 ms	79752 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef long long lint;
typedef pair<lint,lint> ii;

int taken[1505];
bool takelow[1505][1505];
bool takehigh[1505][1505];

vector<int> small[1505];
vector<int> big[1505];

vector<vector<int>> arr;
int n, m;

long long find_maximum(int k, vector<vector<int>> ARR){
	arr = ARR;
	
	n = arr.size(), m = arr[0].size();
	
	vector<vector<int>> answer;
	
	lint ans = 0;
	
	for(int i = 0;i < n;i++){
		std::vector<int> row(m);
		fill(all(row), -1);
		answer.push_back(row);
	}
	
	for(int i = 0;i < n;i++){
		for(int j = 0;j < k;j++){
			ans -= arr[i][j];
			takelow[i][j] = true;
		}
	}
	
	priority_queue<ii> pq;
	
	for(int color = 0;color < n;color++){
		int t = taken[color];
		lint low = arr[color][k-t-1];
		lint high = arr[color][m-t-1];
		pq.push(ii(low+high, color));
	}
	
	for(int turn = 0;turn < n*k/2;turn++){
		ii T = pq.top(); pq.pop();
		ans += T.first;
		
		int color = T.second;
		int t = taken[color];
		takelow[color][k-t-1] = false;
		takehigh[color][m-t-1] = true;
		
		taken[color]++;
		
		///push stuff into pq
		t = taken[color];
		
		if(t != k){
			lint low = arr[color][k-t-1];
			lint high = arr[color][m-t-1];
			pq.push(ii(low+high, color));
		}
	}
		
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			if(takelow[i][j]) small[i].push_back(j);
			if(takehigh[i][j]) big[i].push_back(j);
		}
	}
	
	for(int turn = 0;turn < k;turn++){
		int needBig = n/2;
		bool taken[n]; fill(taken, taken+n, false);
		
		for(int i = 0;i < n;i++){
			if(sz(big[i]) == 0){
				int p = small[i].back(); small[i].pop_back();
				answer[i][p] = turn;
				taken[i] = true;
			}
			else if(sz(small[i]) == 0){
				int p = big[i].back(); big[i].pop_back();
				answer[i][p] = turn;
				needBig--;
				taken[i] = true;
			}
		}

		for(int i = 0;i < n;i++){
			if(taken[i]) continue;
			if(needBig != 0){
				int p = big[i].back(); big[i].pop_back();
				answer[i][p] = turn;
				needBig--;
			}
			else{
				int p = small[i].back(); small[i].pop_back();
				answer[i][p] = turn;
			}
		}
	}

	allocate_tickets(answer);
	
	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