Submission #318630

#	Time	Username	Problem	Language	Result	Execution time	Memory
318630		nikatamliani	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1123 ms	86116 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
#define ll long long
ll find_maximum(int k, vector < vector < int > > x) {
    #define f first
    #define s second
    int n = x.size();
    int m = x[0].size();
    vector < pair < int, int > > L(n);
    stack < int > s[n], candidates[n];
    priority_queue < pair < int, int > > q;
    ll answer = 0; 
    for(int p = 0; p < n; ++p) {
        L[p].s = p; 
        for(int i = m - 1; i >= m - k; --i) {
            s[p].push(x[p][i]);
            answer += x[p][i];
        }
        for(int i = m - 1; i >= 0; --i) {
            candidates[p].push(x[p][i]); 
        }
        if(!s[p].empty() && !candidates[p].empty()) {
            q.push({-(s[p].top() + candidates[p].top()), p});
        }
    }
    for(int rep = 0; rep < n * k / 2; ++rep) {
        assert(q.size() > 0);
        auto [x, y] = q.top();
        q.pop();
        s[y].pop();
        candidates[y].pop();
        answer += x; 
        ++L[y].f;
        if(!s[y].empty() && !candidates[y].empty()) {
            q.push({-(s[y].top() + candidates[y].top()), y});
        }
    }
    vector < vector < int > > less(n, vector < int >()), more(n, vector < int >());
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < L[i].f; ++j) {
            less[i].push_back(j);
        }
        for(int j = m - (k - L[i].f); j < m; ++j) {
            more[i].push_back(j);
        }
    }
    vector < vector < int > > ans(n, vector < int > (m, -1));
    for(int i = 0; i < k; ++i) {
        sort(L.rbegin(), L.rend());
        for(int j = 0; j < n / 2; ++j) {
            assert(L[j].f > 0);
            assert(less[L[j].s].size() > 0);
            ans[L[j].second][less[L[j].s].back()] = i;
            --L[j].f;
            less[L[j].s].pop_back();
        }
        for(int j = n / 2; j < n; ++j) {
            assert(more[L[j].s].size() > 0);
            ans[L[j].second][more[L[j].s].back()] = i;
            more[L[j].s].pop_back();
        }
    }
    allocate_tickets(ans);
    return answer;
}
// int main() {
//     cout << find_maximum(1, {{5, 9}, {1, 4}, {3, 6}, {2, 7}}) << '\n';
// }

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         auto [x, y] = q.top();
      |              ^

• 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