Submission #1208044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208044		shmax	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	500 ms	54476 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;
template<typename T>
using vec = vector<T>;
#define i32 int32_t
#define int long long
#define len(x) ((int)(x).size())

long long find_maximum(i32 k, std::vector<std::vector<i32>> x) {
    int n = x.size();
    int m = x[0].size();
    vec<vec<i32>> d(n, vec<i32>(m, -1));
//    allocate_tickets(vec<vec<i32>>(n, vec<i32>(m, 0)));
    int S = 0;
    set<pair<int, int>> deltas;
    vec<int> ptr(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = m - k; j < m; j++) {
            S += x[i][j];
        }
        deltas.emplace(-x[i][m - k + ptr[i]] - x[i][ptr[i]], i);
//        deltas.emplace(-x[i].back() - x[i][0], i);
    }
    for (int t = 0; t < n * k / 2; t++) {
        auto [xy, i] = *deltas.rbegin();
        deltas.erase(prev(deltas.end()));
        S += xy;
        d[i][m - k + ptr[i]] = -1;
        ptr[i]++;
        if (ptr[i] < k) {
            deltas.emplace(-x[i][m - k + ptr[i]] - x[i][ptr[i]], i);
        }
    }
//    vec<pair<int, int>> mins;
//    vec<pair<int, int>> maxs;
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            if (d[i][j] == 1) {
//                mins.emplace_back(i, j);
//            } else if (d[i][j] == -1) {
//                maxs.emplace_back(i, j);
//            }
//        }
//    }
    vec<int> bd(n, 0);
    for (int t = 0; t < k; t++) {
        vec<int> ids(n);
        iota(ids.begin(), ids.end(), 0);
        sort(ids.rbegin(), ids.rend(), [&](int i, int j) {
            return ptr[i] < ptr[j];
        });
        for (int i = 0; i < n / 2; i++) {
            d[ids[i]][ptr[ids[i]]-1] = t;
            ptr[ids[i]]--;
        }
        for (int i = n / 2; i < n; i++) {
            d[ids[i]][m - 1 - bd[ids[i]]] = t;
            bd[ids[i]]++;
        }
    }
    allocate_tickets(d);
    return S;
}

• 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