Submission #358554

#	Time	Username	Problem	Language	Result	Execution time	Memory
358554		Jasiekstrz	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	751 ms	60396 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x)
{
	int n = x.size();
	int m = x[0].size();
	int i,j;
	vector<int> it[2];
	vector<vector<int>> ans;
	long long w=0;
	for(i=0;i<n;i++)
	{
		it[0].push_back(0);
		it[1].push_back(m-1);
	}
	for(i=0;i<n;i++)
	{
		ans.push_back({});
		for(j=0;j<m;j++)
			ans.back().push_back(-1);
	}
	while(k--)
	{
		priority_queue<pair<int,int>> pq;
		for(i=0;i<n;i++)
		{
			pq.push({-x[i][it[1][i]]-x[i][it[0][i]],i});
			w+=x[i][it[1][i]];
		}
		for(i=0;i<n/2;i++)
		{
			int xd=pq.top().second;
			w+=pq.top().first;
			pq.pop();
			ans[xd][it[0][xd]++]=k;
		}
		while(!pq.empty())
		{
			int xd=pq.top().second;
			pq.pop();
			ans[xd][it[1][xd]--]=k;
		}
	}
	allocate_tickets(ans);
	return w;
}

• 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