Submission #419583

#	Time	Username	Problem	Language	Result	Execution time	Memory
419583		vkgainz	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	910 ms	67316 KiB

tickets

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

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

int64_t find_maximum(int k, vector<vector<int>> x) {
    int n = (int) x.size(), m = (int) x[0].size();
    vector<vector<int>> assign(n, vector<int>(m, -1));
    int64_t ans = 0;
    vector<pair<int, int>> c;
    vector<int> take(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < k; j++) {
            ans -= x[i][j];
        }
        for(int b = k - 1; b >= 0; b--) {
            c.push_back({x[i][b + m - k] + x[i][b], i});
        }
    }
    sort(c.begin(), c.end());
    for(int i = 0; i < n * k / 2; i++) {
        take[c.back().second]++;
        ans += c.back().first;
        c.pop_back();
    }
    int l = 0, r = k - 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < take[i]; j++) {
            assign[i][m - 1 - j] = r;
            --r;
            if(r < 0) r += k;
        }
        for(int j = 0; j < k - take[i]; j++) {
            assign[i][j] = l;
            ++l;
            if(l == k) l -= k;
        }
    }
    allocate_tickets(assign);
    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