Submission #1008063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008063		Mizo_Compiler	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	591 ms	75348 KiB

tickets

#include <bits/stdc++.h>
using namespace std;
#include "tickets.h"
typedef long long ll;
#define F first
#define S second
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define pb push_back
const int N = 1505;
int tk[N], n, m, k;
vector<vector<int>> a;
vector<int> vv[N], vv2[N];

ll gt(int id) {
    if (tk[id] == k)return 1e18;
    return (a[id][k-1-tk[id]] + a[id][m-1-tk[id]]);
}

ll find_maximum(int ko, vector<vector<int>> xx) {
    a = xx;
    n = sz(a);
    m = sz(a[0]);
    k = ko;
    a = xx;
    ll ans = 0;
    set<pair<ll, int>> s;
    for (int i = 0; i < n; i++) {
        tk[i] = 0;
        vv[i].clear();
        vv2[i].clear();
        sort(all(a[i]), greater<>());
        for (int j = 0; j < k; j++) {
            ans += a[i][j];
        }
        s.insert({gt(i), i});
    }
    int cnt = (n >> 1) * k;
    while (cnt--) {
        ll x = s.begin()->F;
        int i = s.begin()->S;
        s.erase(s.begin());
        ans -= x;
        ++tk[i];
        s.insert({gt(i), i});

    }
    vector<vector<int>> res(n, vector<int> (m, -1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= k-1-tk[i]; j++) {
            vv[i].pb(m-j-1);
        }
        for (int j = m-1; j > m-1-tk[i]; j--) {
            vv2[i].pb(m-j-1);
        }
    }
    for (int ii = 0; ii < k; ii++) {
        vector<pair<int, int>> vo;
        for (int i = 0; i < n; i++)vo.pb({sz(vv[i]), i});
        sort(all(vo));
        for (int i = 0; i < n; i++) {
            int cur = vo[i].S;
            if (i < n/2) {
                res[cur][vv2[cur].back()] = ii;
                vv2[cur].pop_back();
            } else {
                res[cur][vv[cur].back()] = ii;
                vv[cur].pop_back();
            }
        }
    }
    allocate_tickets(res);
    return ans;
}

/*int main() {
    int nn, mm, kk;
    cin >> nn >> mm >> kk;
    vector<vector<int>> vvv(nn, vector<int>(mm));
    for (int i = 0; i < nn; i++) {
        for (int j = 0; j < mm; j++) {
            cin >> vvv[i][j];
        }
    }
    cout << find_maximum(kk, vvv);
}*/

• 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