Submission #1239590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239590		Ghulam_Junaid	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	535 ms	54296 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], mxp[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] = mxp[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});
    }

    for (int round = 0; round < k; round ++){
        vector<int> mins, maxs;
        while (!pq.empty()) pq.pop();
        for (int i = 0; i < n; i ++){
            if (mx[i] == 0) mins.push_back(i);
            else if (mn[i] == 0) maxs.push_back(i);
            else pq.push({x[i][mn[i] - 1], i});
        }

        while (mins.size() < n / 2){
            mins.push_back((pq.top()).second);
            pq.pop();
        }
        while (pq.size()){
            maxs.push_back((pq.top()).second);
            pq.pop();
        }

        for (int i : mins){
            output[i][mn[i] - 1] = round;
            mn[i]--;
        }
        for (int i : maxs){
            output[i][m - mxp[i] - 1] = round;
            mxp[i]++;
            mx[i]--;
        }
    }

	allocate_tickets(output);
	return res;
}

• 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