Submission #1066412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066412		ArthuroWich	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1032 ms	86180 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
    int n = x.size(), m = x[0].size();
    vector<vector<int>> answer(n, vector<int>(m, -1));
    long long int ans = 0;
    priority_queue<tuple<int, int, int>> pq;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            pq.push({x[i][j]+x[i][m-k+j], i, j});
        }
    }
    vector<vector<int>> l(n), r(n);
    for (int j = 0; j < n*k/2; j++) {
        auto [v, i, j1] = pq.top();
        pq.pop();
        ans += x[i][m-k+j1];
        r[i].push_back(m-k+j1);
    }
    while(!pq.empty()) {
        auto [v, i, j1] = pq.top();
        pq.pop();
        ans -= x[i][j1];
        l[i].push_back(j1);
    }
    priority_queue<pair<int, int>> a;
    for (int j = 0; j < k; j++) {
        for (int i = 0; i < n; i++) {
            a.push({r[i].size(), i});
        }
        for (int x = 0; x < n/2; x++) {
            auto [_, ind] = a.top();
            a.pop();
            int v = r[ind].back();
            r[ind].pop_back();
            answer[ind][v] = j;
        }
        for (int x = 0; x < n/2; x++) {
            auto [_, ind] = a.top();
            a.pop();
            int v = l[ind].back();
            l[ind].pop_back();
            answer[ind][v] = j;
        }
    }
    allocate_tickets(answer);
    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