Submission #419562

#	Time	Username	Problem	Language	Result	Execution time	Memory
419562		vkgainz	Carnival Tickets (IOI20_tickets)	C++17	16 / 100	697 ms	60660 KiB

tickets

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

struct ins {
    int val, sidx, lidx, idx;
};

bool cmp(ins &x, ins &y) { 
    if(x.val == y.val) return x.idx < y.idx;
    return x.val < y.val;
}

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 a = n - 1, b = k - 1; b >= 0; a--, b--) {
            c.push_back({x[i][a] + 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][n - 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: 0 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10