Submission #513880

#	Time	Username	Problem	Language	Result	Execution time	Memory
513880		AdamGS	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	703 ms	93900 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1507;
ll T[LIM][LIM], akt[LIM], ilea[LIM], ileb[LIM], n, m;
ll find_maximum(int k, vector<vector<int>>V) {
	n=V.size();
	m=V[0].size();
	rep(i, n) rep(j, m) T[i][j]=V[i][j];
	ll sum=0;
	rep(i, n) rep(j, k) sum+=T[i][m-j-1];
	priority_queue<pair<ll,int>>q;
	rep(i, n) q.push({-T[i][0]-T[i][m-k], i});
	rep(i, n*k/2) {
		ll p=q.top().st, a=q.top().nd; q.pop();
		sum+=p;
		++akt[a];
		if(akt[a]<k) q.push({-T[a][akt[a]]-T[a][m-k+akt[a]], a});
	}
	vector<vector<int>>ans;
	rep(i, n) {
		vector<int>p;
		rep(j, m) p.pb(-1);
		ans.pb(p);
	}
	rep(i, k) {
		vector<pair<int,int>>p;
		rep(j, n) p.pb({akt[j]-ilea[j], j});
		sort(all(p));
		reverse(all(p));
		rep(j, n) {
			int x=p[j].nd;
			if(j<n/2) {
				ans[x][ilea[x]]=i;
				++ilea[x];
			} else {
				++ileb[x];
				ans[x][m-ileb[x]]=i;
			}
		}
	}
	allocate_tickets(ans);
	return sum;
}

• 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