Submission #321479

#	Time	Username	Problem	Language	Result	Execution time	Memory
321479		grt	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	887 ms	76612 KiB

tickets

#include <bits/stdc++.h>

using namespace std;

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

#define ST first
#define ND second
#define PB push_back

const int nax = 1500 + 10;
int take[nax];

void allocate_tickets(vector<vi> a);

ll find_maximum(int k, vector<vi>x) {
    int n = (int)x.size();
    int m = (int)x[0].size();
    ll ans = 0;
    for(int i = 0; i < k; ++i) {
        for(int j = 0; j < n; ++j) {
            ans -= x[j][i];
        }
    }
    priority_queue<pi>PQ;
    for(int i = 0; i < n; ++i) {
        take[i] = 0;
        PQ.push({x[i][m - 1] + x[i][k - 1], i});
    }
    int cur = 0;
    while(cur < n * k / 2) {
        cur++;
        pi tp = PQ.top();
        ans += tp.ST;
        PQ.pop();
        take[tp.ND]++;
        if(take[tp.ND] < k) {
            PQ.push({x[tp.ND][m - 1 - take[tp.ND]] + x[tp.ND][k - 1 - take[tp.ND]], tp.ND});
        }
    }
    vector<vi>res(n);
    for(int i = 0; i < n; ++i) res[i].resize(m, -1);
    vector<vector<bool>>t(n);
    for(int i = 0; i < n; ++i) t[i].resize(k+1);
    for(int turn = k - 1; turn >= 0; --turn) {
        cur = 0;
        for(int i = 0; i < n; ++i) {
            if(take[i] == turn + 1) {
                t[i][turn] = 1;
                cur++;
                continue;
            } else if(take[i] == 0) {
                t[i][turn] = 0;
                cur--;
                continue;
            }
        }
        for(int i = 0; i < n; ++i) {
            if(take[i] == turn + 1 || take[i] == 0) continue;
            if(cur < 0) {
                t[i][turn] = 1;
                cur++;
            } else {
                t[i][turn] = 0;
                cur--;
            }
        }
        for(int i = 0; i < n; ++i) {
            if(t[i][turn]) take[i]--;
        }
    }
    vi l(n, 0);
    vi r(n, m-1);
    for(int turn = 0; turn < k; ++turn) {
        for(int i = 0; i < n; ++i) {
            if(t[i][turn]) {
                res[i][r[i]--] = turn;
            } else {
                res[i][l[i]++] = turn;
            }
        }
    }
    allocate_tickets(res);
    //for(int i = 0; i < n; ++i) {
    //    for(int j = 0; j < m; ++j) {
    //        cout << res[i][j] << " ";
    //    }
    //    cout << "\n";
    //}
    return ans;
}

//int main() {
 //   cout << find_maximum(2, {{0, 2, 5},{1, 1, 3}}) << "\n";
 //   cout << find_maximum(1, {{5, 9}, {1, 4}, {3, 6}, {2, 7}}) << "\n";
//}

• 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