Submission #409460

#	Time	Username	Problem	Language	Result	Execution time	Memory
409460		achibasadzishvili	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	639 ms	52484 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;
	}
	for(int val=0; val<k; val++){
		vector<pair<int,int> >v;
		for(int i=0; i<n; i++){
			v.pb({ind[i] , i});
		}
		sort(v.begin() , v.end());
		int P = 0;
		for(auto to : v){
			P++;
			int i = to.s;
			if(P > n / 2){
				ans[i][l[i]] = val;
				l[i]++;
			}
			else{
				ans[i][r[i]] = val;
				r[i]--;
			}
		}
	}
	allocate_tickets(ans);
	return pas;
}

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