Submission #409463

#	Time	Username	Problem	Language	Result	Execution time	Memory
409463		achibasadzishvili	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1104 ms	62136 KiB

tickets

#include "tickets.h"
#include <vector>
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll l[50005],r[50005],t[50005],ind[50005];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = (int)x.size() , m = (int)x[0].size();
	vector<vector<int> >ans;
	vector<int>g;
	ll pas = 0;
	for(int i=0; i<m; i++)
		g.pb(-1);
	for(int i=0; i<n; i++)ans.pb(g);
	for(int i=0; i<k; i++){
		t[i] = m - 1 - (k - i - 1);
	}
	set<pair<ll,ll> >st;
	for(int i=0; i<n; i++){
		sort(x[i].begin() , x[i].end());
		for(int j=0; j<k; j++){
			pas -= x[i][j];
		}
		ind[i] = k - 1;
		st.insert({x[i][ind[i]] + x[i][t[ind[i]]] , i});
	}
	ll raod = n * k / 2;
	while(raod--){
		pair<ll,ll>p = *(--st.end());
		pas += p.f;
		st.erase(st.find(p));
		ll a = p.s;
		ind[a]--;
		if(ind[a] >= 0){
			st.insert({x[a][ind[a]] + x[a][t[ind[a]]] , a});
		}
	}
	for(int i=0; i<n; i++){
		l[i] = 0;
		r[i] = m - 1;
	}
	pas = 0;
	//cout << k << '\n';
	for(int val=0; val<k; val++){
		vector<pair<int,int> >v;
		for(int i=0; i<n; i++){
			//cout << i << " " << ind[i] << '\n';
			v.pb({ind[i] , i});
		}
		sort(v.begin() , v.end());
		int P = 0;
		//cout << val << " " << '\n';
		for(auto to : v){
			P++;
			int i = to.s;
			if(P > n / 2){
				ans[i][l[i]] = val;
				pas -= x[i][l[i]];
				l[i]++;
				ind[i]--;
			}
			else{
				pas += x[i][r[i]];
				ans[i][r[i]] = val;
				r[i]--;
			}
		}
	}
	allocate_tickets(ans);
	return pas;
}

• 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