Submission #1061559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061559		vjudge1	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	317 ms	51624 KiB

tickets

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

using vi = vector<int>;
using ll = long long;
using ii = pair<int, int>;
using vll = vector<ll>;

ll find_maximum(int k, vector<vi> x) {
	int n = x.size();
	int m = x[0].size();
    vll Sum(n, 0), CntPlus(n, 0);
    auto calc = [&](int cul, int nr) { // cat as castiga
        return x[cul][m - 1 - nr] + x[cul][k - 1 - nr];
    };
    priority_queue<pair<ll, int> > PQ;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < k; ++j) {
            Sum[i] -= x[i][j];
        }
        PQ.push({calc(i, 0), i});
    }
    for(int nr = 0; nr < n * k / 2; ++nr) {
        auto [delta, cul] = PQ.top();
        PQ.pop();
        ++CntPlus[cul];
        Sum[cul] += delta;
        if(CntPlus[cul] < k) {
            PQ.push({calc(cul, CntPlus[cul]), cul});
        }
    }
    ll re = 0;
    //for(auto it : Sum) re += it;

    vector<vector<ii>> Plus(n), Minus(n);

    vector<vi> S(n, vi(m, -1));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < k - CntPlus[i]; ++j)
            Minus[i].push_back({i, j});
        for(int j = 0; j < CntPlus[i]; ++j)
            Plus[i].push_back({i, m - 1 - j});
    }
    for(int nr = 0; nr < k; ++nr) {
        vi Neutre;
        vector<ii> Luate;
        int sum = 0;
        for(int i = 0; i < n; ++i) {
            if(Plus[i].size() == Minus[i].size()) {
                Neutre.push_back(i);
                continue;
            }
            if(Plus[i].size() > Minus[i].size()) {
                Luate.push_back(Plus[i].back());
                Plus[i].pop_back();
                ++sum;
            } else {
                Luate.push_back(Minus[i].back());
                Minus[i].pop_back();
                --sum;
            }
        }
        for(auto i : Neutre) {
            if(sum < 0) {
                Luate.push_back(Plus[i].back());
                Plus[i].pop_back();
                ++sum;
            } else {
                Luate.push_back(Minus[i].back());
                Minus[i].pop_back();
                --sum;
            }
        }
        vi Val;
        for(auto [c, p] : Luate) {
            S[c][p] = nr;
            Val.push_back(x[c][p]);
        }
        sort(Val.begin(), Val.end());
        for(int i = 0; i < n; ++i) {
            if(i < n / 2) re -= Val[i];
            else re += Val[i];
        }
    }
    allocate_tickets(S);
    return re;
}

• 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