Submission #1133033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133033		urosk	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	468 ms	72140 KiB

tickets

#include "tickets.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld,ld>;

const ll maxn = 1505;
ll a[maxn][maxn];
ll c[maxn];
ll l[maxn],r[maxn];
ll g[maxn];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	ll n,m;
	n = si(x);
    m = si(x[0]);
    for(ll i = 1;i<=n;i++) for(ll j = 1;j<=m;j++) a[i][j] = x[i-1][j-1];
	for(ll i = 1;i<=n;i++) a[i][0] = llinf;
	for(ll i = 1;i<=n;i++) a[i][m+1] = -llinf;
    ll ans = 0;
    priority_queue<pll> pq;
    ll cnt = n*k/2;
    for(ll i = 1;i<=n;i++){
      c[i] = k;
      for(ll j = 1;j<=k;j++) ans-=a[i][j];
      pq.push({a[i][m]+a[i][k],i});
    }
    while(cnt--){
    	pll p = pq.top(); pq.pop();
        ll i = p.sc;
        ans+=p.fi;
        c[i]--;
        if(c[i]) pq.push({a[i][c[i]]+a[i][m-(k-c[i])],i});
    }
	vector<vector<int> > id;
	id.resize(n);
	for(ll i = 0;i<n;i++) {
		id[i].resize(m);
		for(int& j : id[i]) j = -1;
	}
	vector<ll> it;
	it.resize(n);
	iota(all(it),1);
	for(ll i = 1;i<=n;i++) {
		r[i] = m,l[i] = 1;
		if(c[i]==0) g[i] = 0;
		if(c[i]==k) g[i] = m+1;
	}
	for(ll R = 0;R<k;R++) {
		iota(all(it),1);
		sort(all(it),[](const int x,const int y) {
			return c[x]>c[y];
		});
		vector<ll> w;
		for(ll j = 0;j<n/2;j++) {
			ll i = it[j];
			id[i-1][l[i]-1] = R;
			l[i]++;
			c[i]--;
		}
		for(ll j = n/2;j<n;j++) {
			ll i = it[j];
			id[i-1][r[i]-1] = R;
			r[i]--;
		}
	}
	allocate_tickets(id);
	return ans;
}
/*
2 3 2
0 2 5
1 1 3

4 2 1
5 9
1 4
3 6
2 7
*/

• 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