Submission #1139815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139815		garam1732	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	699 ms	99592 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 1515;//100100*5;
const ll MOD = 1e9+7;
const ll INF = 2e9;

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

std::vector<std::vector<int>> res;
priority_queue<ipi> pq;
vector<int> v[MAXN], w[MAXN];
bitset<MAXN> chk;

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

    res.resize(n); for(auto &x:res) x.resize(m, -1);

    ll ans=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<k; j++) {
            pq.push(ipi(x[i][j]+x[i][j+m-k], pi(i,j+m-k)));
            ans -= x[i][j]; w[i].push_back(j);
        }
    }
	
	for(int i=0; i<k*n/2; i++) {
        auto x = pq.top(); pq.pop();
        ans += x.ff;

        v[x.ss.ff].push_back(x.ss.ss);
        w[x.ss.ff].pop_back();
    }

    for(int t=k; t>0; t--) {
        int cnt = n/2; chk.reset();
        for(int i=0; i<n; i++) {
            if(v[i].size()==t) {
                cnt--;
                res[i][v[i].back()] = t-1;
                v[i].pop_back();
                chk[i] = 1;
            }
        }

        for(int i=0; i<n; i++) {
            if(cnt==0) break;
            if(!chk[i] && v[i].size()) {
                cnt--;
                res[i][v[i].back()] = t-1;
                v[i].pop_back();
                chk[i] = 1;
            }
        }

        for(int i=0; i<n; i++) {
            if(!chk[i]) {
                res[i][w[i].back()] = t-1;
                w[i].pop_back();
            }
        }
    }

	allocate_tickets(res);
	return ans;
}

• 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