Submission #309504

#	Time	Username	Problem	Language	Result	Execution time	Memory
309504		knon0501	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1421 ms	99788 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int L[1501];
queue<int> A[1501];
queue<int> B[1501];
int ss[1501];
queue<int> aa[1501];
queue<int> bb[1501];
queue<pair<int,int>> Q[1501];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	std::vector<std::vector<int>> answer(n);
	int i,j;
	for(int i=0 ; i<n ; i++)answer[i].resize(m);

	for(i=0 ; i<n ; i++)for(j=0 ; j<m ; j++)answer[i][j]=-1;

	priority_queue<pair<int,int>> Q2;
	for(i=0 ; i<n ; i++){
        for(j=1 ; j<=k ; j++){
            Q[i].push({x[i][k-j]+x[i][m-j],j});
        }
        Q2.push({Q[i].front().first,i});
	}

	vector<pair<int,pair<int,int>>> v;
	for(i=0 ; i<n*k/2 ; i++){
        int t=Q2.top().second;
        Q2.pop();
        Q[t].pop();
        if(!Q[t].empty())Q2.push({Q[t].front().first,t});
	}

	for(i=0 ; i<n ; i++){
        int y;
        if(Q[i].empty())y=0;
        else y=Q[i].size();
        for(j=0 ; j<y ; j++)v.push_back({x[i][j],{i,j}});
        for(j=m-(k-y) ; j<m ; j++)v.push_back({x[i][j],{i,j}});
	}


    sort(v.begin(),v.end());
    long long ans=0;
    for(i=0 ; i<n*k/2 ; i++){
        aa[v[i].second.first].push(v[i].second.second);
        ans-=v[i].first;
    }
    for(i=n*k/2 ; i<n*k ; i++){
        bb[v[i].second.first].push(v[i].second.second);
        ans+=v[i].first;
    }


    for(j=0 ; j<k ; j++){
        vector<pair<int,int>> vv;
        for(i=0 ; i<n ; i++)vv.push_back({bb[i].size(),i});
        sort(vv.begin(),vv.end());
        for(i=0 ; i<n/2 ; i++){
            answer[vv[i].second][aa[vv[i].second].front()]=j;
            aa[vv[i].second].pop();

        }
        for(i=n/2 ; i<n ; i++){
            answer[vv[i].second][bb[vv[i].second].front()]=j;
            bb[vv[i].second].pop();
        }
    }
	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