Submission #800155

#	Time	Username	Problem	Language	Result	Execution time	Memory
800155		PixelCat	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	1 ms	724 KiB

tickets

#include "tickets.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

// int cost_single(int n, vector<int> v) {
//     sort(all(v));
//     int s = 0;
//     int m = n / 2;
//     For(i, 0, m - 1) {
//         s += v[n - i - 1] - v[i];
//     }
//     return s;
// }

// int cost(int n, int m, int k, vector<vector<i32>> &x, vector<vector<i32>> &ans) {
//     vector<vector<int>> game(k);
//     For(i, 0, n - 1) For(j, 0, m - 1) if(ans[i][j] != -1) {
//         game[ans[i][j]].eb(x[i][j]);
//     }
//     int res = 0;
//     for(auto &g:game) res += cost_single(n, g);
//     return res;
// }

struct Ayaya {
    int val, i, j;
    Ayaya(int _val, int _i, int _j): val(_val), i(_i), j(_j) {}
    bool operator<(const Ayaya &rhs) const {
        return val < rhs.val;
    }
    bool operator>(const Ayaya &rhs) const {
        return val > rhs.val;
    }
};

int find_maximum(i32 _k, vector<vector<i32>> x) {
    int k = _k;
    int n = sz(x);
    int m = sz(x[0]);
    vector<vector<i32>> answer(n, vector<i32>(m, -1));
    int cost = 0;

    priority_queue<Ayaya> big;
    For(i, 0, n - 1) {
        big.emplace(x[i][m - 1], i, m - 1);
    }
    For(_, 1, n * k / 2) {
        auto aya = big.top(); big.pop();
        answer[aya.i][aya.j] = -2;
        cost += aya.val;
        if(m - aya.j < k) {
            big.emplace(x[aya.i][aya.j - 1], aya.i, aya.j);
        }
    }

    priority_queue<Ayaya, vector<Ayaya>, greater<Ayaya>> smol;
    For(i, 0, n - 1) if(answer[i][0] == -1) {
        smol.emplace(x[i][0], i, 0);
    }
    For(_, 1, n * k / 2) {
        auto aya = smol.top(); smol.pop();
        answer[aya.i][aya.j] = -3;
        cost -= aya.val;
        if(aya.j < k - 1 && answer[aya.i][aya.j + 1] == -1) {
            smol.emplace(x[aya.i][aya.j + 1], aya.i, aya.j + 1);
        }
    }

    i32 cnt = 0;
    For(i, 0, n - 1) For(j, 0, m - 1) if(answer[i][j] == -2) {
        answer[i][j] = cnt;
        cnt++;
        cnt -= _k * (cnt >= _k);
    }
    cnt = 0;
    For(i, 0, n - 1) For(j, 0, m - 1) if(answer[i][j] == -3) {
        answer[i][j] = cnt;
        cnt++;
        cnt -= _k * (cnt >= _k);
    }

    allocate_tickets(answer);
    return cost;  //(n, m, k, x, answer);
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10