Submission #769409

#	Time	Username	Problem	Language	Result	Execution time	Memory
769409		t6twotwo	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	537 ms	58352 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll find_maximum(int K, vector<vector<int>> x) {
    int N = x.size();
    int M = x[0].size();
    ll ans = 0;
    vector<int> f(N, K);
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K; j++) {
            ans -= x[i][j];
        }
        pq.emplace(x[i][K - 1] + x[i][M - 1], i);
    }
    for (int i = 0; i < N * K / 2; i++) {
        auto [v, p] = pq.top();
        pq.pop();
        ans += v;
        if (--f[p]) {
            pq.emplace(x[p][f[p] - 1] + x[p][M - (K - f[p]) - 1], p);
        }
    }
    vector a(N, vector<int>(M, -1));
    int s = 0, t = K - 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < f[i]; j++) {
            a[i][j] = s++;
            if (s == K) {
                s = 0;
            }
        }
        for (int j = M - (K - f[i]); j < M; j++) {
            a[i][j] = t--;
            if (t == -1) {
                t = K - 1;
            }
        }
    }
    allocate_tickets(a);
    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