Submission #1259346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259346		biank	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	428 ms	54344 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
 
#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)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
#define pb push_back
#define eb emplace_back
 
#define fst first
#define snd second
 
using namespace std;
 
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;


ll find_maximum(int k, vector<vi> x) {
    int n = sz(x), m = sz(x[0]);
    ll ret = 0;
    int sub = n * k, sum = 0;
    forn(i, n) forn(j, k) ret -= x[i][j];
    vi pos(n, 0);
    priority_queue<pair<ll, int>> pq;
    forn(i, n) pq.emplace(x[i][k - 1] + x[i][m - 1], i);
    while (sub != sum) {
        auto [diff, i] = pq.top();
        pq.pop(), sub--, sum++, ret += diff, pos[i]++;
        if (k - pos[i] - 1 >= 0) pq.emplace(x[i][k - 1 - pos[i]] + x[i][m - 1 - pos[i]], i);
    }
    vi left(n), right(n);
    forn(i, n) left[i] = k - pos[i], right[i] = pos[i];
    vector<vi> ans(n, vi(m, -1));
    forn(r, k) {
        vi order(n);
        iota(all(order), 0);
        sort(all(order), [&](const int &lhs, const int &rhs) {
            return right[lhs] > right[rhs];
        });
        forn(idx, n / 2) {
            int i = order[idx];
            assert(right[i] >= 1);
            ans[i][m - right[i]] = r;
            right[i]--;
        }
        forsn(idx, n / 2, n) {
            int i = order[idx];
            assert(left[i] >= 1);
            ans[i][left[i] - 1] = r;
            left[i]--;
        }
    }
    allocate_tickets(ans);
    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