Submission #576610

#	Time	Username	Problem	Language	Result	Execution time	Memory
576610		nghiass001	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	657 ms	75904 KiB

tickets

#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define pii pair<int, int>
using namespace std;
const int INF = 0x3c3c3c3c;

void allocate_tickets( vector<vector<int>> _x);

long long find_maximum(int k, vector<vector<int>> d) {
    int n = d.size(), m = d[0].size();
    vector<int> num(n, 0);
    vector<int> a(n), cnt_left(n), lft(n, 0), rgt(n, m - 1);
    vector<vector<int>> ans(n, vector<int>(m, -1));
    long long res = 0;

    priority_queue<pii, vector<pii>, greater<pii>> Q;
    REP(i, 0, n) Q.emplace(d[i][0] + d[i][m - k], i);

    REP(i, 0, n * k / 2) {
        auto [val, u] = Q.top(); Q.pop();
        if (++num[u] < k) {
            int new_val = d[u][num[u]] + d[u][m - k + num[u]];
            Q.emplace(new_val, u);
        }
    }

    REP(i, 0, n) cnt_left[i] = num[i];
    REP(i, 0, n) a[i] = i;

    REP(i, 0, k) {
        sort(a.begin(), a.end(), [&] (int x, int y) { return cnt_left[x] < cnt_left[y]; });
        REP(j, 0, n) {
            int u = a[j];
            if (j < n/2) {
                ans[u][rgt[u]] = i;
                res += d[u][rgt[u]--];
            }
            else {
                --cnt_left[u];
                ans[u][lft[u]] = i;
                res -= d[u][lft[u]++];
            }
        }
    }

    allocate_tickets(ans);
    return res;
}

• 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