Submission #1066402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066402		ArthuroWich	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1002 ms	134052 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
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));
    vector<deque<pair<int, int>>> t(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            t[i].push_back({x[i][j], j});
        }
    }
    long long int ans = 0;
    priority_queue<tuple<int, int, int, int>> pq;
    vector<pair<int, int>> left, right;
    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, m-k+j});
        }
    }
    for (int j = 0; j < n*k/2; j++) {
        auto [v, i, j1, j2] = pq.top();
        pq.pop();
        right.push_back({i, j2});
    }
    while(!pq.empty()) {
        auto [v, i, j1, j2] = pq.top();
        pq.pop();
        left.push_back({i, j1});
    }
    vector<vector<int>> l(n), r(n);
    for (auto [i, j] : left) {
        ans -= x[i][j];
        l[i].push_back(j);
    }
    for (auto [i, j] : right) {
        ans += x[i][j];
        r[i].push_back(j);
    }
    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