제출 #1308017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308017		biank	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	489 ms	73064 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define sum(x) accumulate(all(x), 0LL)

#define pb push_back
#define eb emplace_back

#define fst first
#define snd second

ll find_maximum(int k, vector<vi> x) {
    const int n = sz(x), m = sz(x[0]);
    vector<vi> left(n), right(n);
    ll ret = 0;
    forn(i, n) forn(j, k) left[i].pb(j), ret -= x[i][j];
    priority_queue<pair<ll, int>> pq;
    forn(i, n) pq.emplace(x[i][left[i].back()] + x[i].back(), i);
    forn(_, n * k / 2) {
        auto [diff, i] = pq.top(); pq.pop();
        left[i].pop_back();
        x[i].pop_back();
        right[i].pb(sz(x[i]));
        ret += diff;
        if (!left[i].empty()) pq.emplace(x[i][left[i].back()] + x[i].back(), i);
    }
    vector<vi> s(n, vi(m, -1));
    forn(step, k) {
        vi colors(n);
        iota(all(colors), 0);
        sort(all(colors), [&](const int &a, const int &b) {
            return sz(left[a]) > sz(left[b]);
        });
        forn(idx, n) {
            int i = colors[idx];
            auto &part = idx < n / 2 ? left[i] : right[i];
            s[i][part.back()] = step;
            part.pop_back();
        }
    }
    allocate_tickets(s);
    return ret;
}

• 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