Submission #1239471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239471		Ghulam_Junaid	Carnival Tickets (IOI20_tickets)	C++20	27 / 100	323 ms	51392 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
// #include "grader.cpp"
using namespace std;

typedef long long ll;

ll find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> output;
    output.resize(n);
    for (int i = 0; i < n; i ++)
        output[i].resize(m, -1);

    ll res = 0;
    int mn[n], mx[n];
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < k; j ++)
            res -= x[i][j];
        mn[i] = k, mx[i] = 0;
        pq.push({x[i][m - mx[i] - 1] + x[i][mn[i] - 1], i});
    }

    int flips = (n / 2) * k;
    while (flips--){
        auto [inc, col] = (pq.top());
        pq.pop();

        res += inc;
        mn[col]--;
        mx[col]++;

        if (mn[col])
            pq.push({x[col][m - mx[col] - 1] + x[col][mn[col] - 1], col});
    }

    int round = 0;
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < mn[i]; j ++, round = (round + 1) % k)
            output[i][j] = round;
        for (int j = m - mx[i]; j < m; j ++, round = (round + 1) % k)
            output[i][j] = round;
    }

	allocate_tickets(output);
	return res;
}

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