Submission #1002382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002382		PoPularPlusPlus	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	503 ms	76332 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second

void allocate_tickets( std::vector<std::vector<int>> _x);

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

	for(int i = 0; i < n; i++){
		sort(all(v[i]));
	}
	ll ans = 0;
	for(int i = 0; i < n; i++){
		for(int j = m - 1; j >= m - k; j--){
			ans += v[i][j];	
		}
	}

	vector<vector<int>> alloc;
	for(int i = 0; i < n; i++){
		vector<int> tp;
		int cnt = k-1;
		for(int j = 0; j < m; j++){
			if(j < m - k)tp.pb(-1);
			else tp.pb(1);
		}
		alloc.pb(tp);
	}

	priority_queue<pair<ll,int>> pq;
	int pos[n];
	memset(pos,0,sizeof pos);
	int pos1[n];
	for(int i = 0; i < n; i++){
		pos1[i] = m - k;
	}
	for(int i = 0; i < n; i++){
		pq.push(mp(-v[i][m-k] - v[i][0], i));
	}

	int temp = (n*k)/2;
	while(temp > 0){
		temp--;
		pair<ll,int> p = pq.top();
		pq.pop();
		ans += p.vf;
		int idx = p.vs;
		alloc[idx][pos1[idx]] = -1;
		alloc[idx][pos[idx]] = 0;
		pos[idx]++;
		pos1[idx]++;
		if(pos1[idx] < m){
			pq.push(mp(-v[idx][pos1[idx]] - v[idx][pos[idx]] , idx));
		}
	}

	int zero[n] , one[n];
	for(int i = 0; i < n; i++){
		zero[i] = pos[i];
		one[i] = m - pos1[i];
	}

	int l[n] , r[n];
	memset(l,0,sizeof l);
	for(int i = 0; i < n; i++){
		r[i] = m - 1;
	}

	for(int tp = 0; tp < k; tp++){
		vector<pair<int,int>> v;
		for(int i = 0; i < n; i++){
			v.pb(mp(one[i] , i));
		}

		sort(all(v));
		for(int i = 0; i < n / 2; i++){
			alloc[v[i].vs][l[v[i].vs]++] = tp;
			zero[v[i].vs]--;
		}
		for(int i = n/2; i < n; i++){
			alloc[v[i].vs][r[v[i].vs]--] = tp;
			one[v[i].vs]--;
		}
	}

	allocate_tickets(alloc);

	return ans;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:30:7: warning: unused variable 'cnt' [-Wunused-variable]
   30 |   int cnt = k-1;
      |       ^~~

• 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