Submission #309405

#	Time	Username	Problem	Language	Result	Execution time	Memory
309405		georgerapeanu	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	995 ms	54520 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer(n,vector<int>(m,-1));
    vector<int> cnt(x.size(),k);
    long long ans = 0;

    for(auto it:x){
        for(int i = 0;i < k;i++){
            ans -= it[i];
        }
    }

    priority_queue<pair<int,int>> pq;

    for(int i = 0;i < n;i++){
        pq.push({x[i][(int)x[i].size() - 1 - (k - cnt[i])] + x[i][cnt[i] - 1],i});
    }

    for(int i = 1;i <= n * k / 2;i++){
        pair<int,int> tmp = pq.top();
        pq.pop();
        cnt[tmp.second]--;
        ans += tmp.first;
        if(cnt[tmp.second] > 0){
            tmp.first = x[tmp.second][(int)x[tmp.second].size() - 1 - (k - cnt[tmp.second])] + x[tmp.second][cnt[tmp.second] - 1];
            pq.push(tmp);
        }
    }

    vector<int> free_left(k,n / 2);

    for(int i = 0;i < n;i++){
        vector<pair<int,int> > tmp;

        for(int j = 0;j < k;j++){
            tmp.push_back({free_left[j],j});
        }

        sort(tmp.begin(),tmp.end());
        reverse(tmp.begin(),tmp.end());

        for(int j = 0;j < cnt[i];j++){
            answer[i][j] = tmp[j].second;
            free_left[tmp[j].second]--;
        }
        for(int j = m - (k - cnt[i]);j < m;j++){
            answer[i][j] = tmp[cnt[i] + (j - (m - (k - cnt[i])))].second;
        }
    }


    allocate_tickets(answer);
	return ans;
}

• 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