Submission #1288430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288430		mariaclara	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	385 ms	54376 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

vi apear, ord;

ll find_maximum(int k, vector<vi> x) {
	int n = sz(x), m = sz(x[0]);
    vi qtd(n);
    ll TOT = 0;
    priority_queue<pii> sub, add;

	for(int i = 0; i < n/2; i++) {
        for(int j = 0; j < k; j++)
            TOT -= x[i][j];
        qtd[i] = k;
        sub.push({x[i][m-1] + x[i][k-1], i});
	}

    for(int i = n/2; i < n; i++) {
        for(int j = m-k; j < m; j++) 
            TOT += x[i][j];
        add.push({- x[i][m-k] - x[i][0], i});
	}

    while(sz(add) and sz(sub)) {
        auto [cost_i, i] = add.top();
        auto [cost_j, j] = sub.top();
        add.pop(); sub.pop();

        if(cost_i + cost_j <= 0) break;
        TOT += cost_i + cost_j;

        qtd[i]++;
        qtd[j]--;

        if(qtd[i] < k) add.push({- x[i][qtd[i]] - x[i][m-k+qtd[i]], i});
        if(qtd[j] > 0) sub.push({x[j][qtd[j]-1] + x[j][m-k+qtd[j]-1], j});
    }

    vector<vi> ans(n, vi(m, -1));

    apear.resize(k);
    ord.resize(k);
    for(int o = 0; o < k; o++) ord[o] = o;

    for(int i = 0; i < n; i++) {
        sort(all(ord), [](int a, int b){
            return mk(apear[a], a) > mk(apear[b], b);
        });

        for(int j = 0; j < qtd[i]; j++) 
            ans[i][j] = ord[j], apear[ord[j]]--;

        for(int j = m-k+qtd[i]; j < m; j++)
            ans[i][j] = ord[j-m+k], apear[ord[j-m+k]]++;
    }

	allocate_tickets(ans);
	return TOT;
}

• 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