Submission #769139

#	Time	Username	Problem	Language	Result	Execution time	Memory
769139		t6twotwo	Carnival Tickets (IOI20_tickets)	C++17	25 / 100	574 ms	79900 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();
    vector<tuple<int, int, int>> v;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            v.emplace_back(x[i][j], i, j);
        }
    }
    sort(v.begin(), v.end());
    vector f(N, vector<int>(M, -1));
    ll ans = 0;
    for (int i = 0; i < N * K / 2; i++) {
        auto [t, x, y] = v[i];
        ans -= t;
        f[x][y] = 0;
    }
    for (int i = N * M - N * K / 2; i < N * M; i++) {
        auto [t, x, y] = v[i];
        ans += t;
        f[x][y] = 1;
    }
    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 < M; j++) {
            if (f[i][j] == 0) {
                a[i][j] = t--;
            }
            if (f[i][j] == 1) {
                a[i][j] = s++;
            }
            if (t == -1) {
                t = K - 1;
            }
            if (s == K) {
                s = 0;
            }
        }
    }
    allocate_tickets(a);
    return ans;
}

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