Submission #1230512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230512		Hamed_Ghaffari	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	469 ms	63256 KiB

tickets

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

using ll = long long;
using pii = pair<int, int>;

#define X first
#define Y second

ll find_maximum(int k, vector<vector<int>> a) {
    int n = a.size(), m = a[0].size();
    vector<vector<int>> ord(n, vector<int>(m));
    ll ans = 0;
    vector<int> cnt(n, 0);
    priority_queue<pii> pq;
    for(int i=0; i<n; i++) {
        iota(ord[i].begin(), ord[i].end(), 0);
        sort(ord[i].begin(), ord[i].end(), [&](int x, int y) {
            return a[i][x] < a[i][y];
        });
        for(int j=0; j<k; j++) ans -= a[i][ord[i][j]];
        pq.push({a[i][ord[i][m-1]]+a[i][ord[i][k-1]], i});
    }
    for(int t=0; t<n*k/2; t++) {
        pii d = pq.top();
        pq.pop();
        ans += d.X;
        if((++cnt[d.Y])<k)
            pq.push({a[d.Y][ord[d.Y][m-1-cnt[d.Y]]]+a[d.Y][ord[d.Y][k-1-cnt[d.Y]]], d.Y});
    }
    vector<int> L(n, 0), R(n, m-1);
    vector<vector<int>> b(n, vector<int>(m, -1));
    for(int r=0; r<k; r++) {
        int ct=0;
        vector<bool> mark(n, 0);
        for(int i=0; i<n; i++)
            if(cnt[i]==k-r) {
                b[i][ord[i][R[i]--]] = r;
                cnt[i]--;
                mark[i] = 1;
                ct++;
            }
        for(int i=0; i<n && ct<n/2; i++)
            if(!mark[i] && cnt[i]) {
                b[i][ord[i][R[i]--]] = r;
                cnt[i]--;
                mark[i] = 1;
                ct++;
            }
        for(int i=0; i<n; i++)
            if(!mark[i])
                b[i][ord[i][L[i]++]] = r;
    }
    allocate_tickets(b);
    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