Submission #354515

#	Time	Username	Problem	Language	Result	Execution time	Memory
354515		juggernaut	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	891 ms	58860 KiB

tickets

//Thank you
#include"tickets.h"
#ifndef EVAL
#include"stub.cpp"
#endif
#include<bits/stdc++.h>
using namespace std;
int l[1505],r[1505];
typedef long long ll;
bool cmp(int x,int y){return (l[x]>l[y]);}
long long find_maximum(int k,vector<vector<int> > arr) {
	priority_queue<pair<ll,int>>q;ll res=0;
	int n=arr.size(),m=arr[0].size();vector<int>ind(n);
	vector<vector<int>>answer(n,vector<int>(m,-1));
	for(int i=0;i<n;i++){ind[i]=i;
		for(int j=0;j<k;j++)res-=arr[i][j];
		q.push({arr[i][l[i]=k-1]+arr[i][r[i]=m-1],i});
	}
	for(int i=0;i<(n*k)>>1;i++){
		int ind=q.top().second;res+=q.top().first;q.pop();--l[ind];--r[ind];
		if(l[ind]>=0)q.push({arr[ind][l[ind]]+arr[ind][r[ind]],ind});
	}
	while(k--){sort(ind.begin(),ind.end(),cmp);	
		for(int i=0;i<n>>1;i++)answer[ind[i]][l[ind[i]]--]=k;
		for(int i=n>>1;i<n;i++)answer[ind[i]][++r[ind[i]]]=k;
	}
	allocate_tickets(answer);
	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