Submission #1043112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043112		MarwenElarbi	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	296 ms	69204 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
#define pb push_back
#define se second
#define fi first
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	long long n = x.size();
	long long m = x[0].size();
	vector<vector<long long>> y(n,vector<long long> (m));
	vector<vector<int>> ans(n,vector<int> (m,-1));
	priority_queue<pair<long long,int>> pq;
	long long res=0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			y[i][j]=x[i][j];
		}
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < k; ++j)
		{
			res-=y[i][j];
		}
	}
	int l[n];
	int r[n];
	for (int i = 0; i < n; ++i)
	{
		l[i]=k-1;
		r[i]=m-1;
		pq.push({y[i][l[i]]+y[i][r[i]],i});
	}
	for (int i = 0; i < 1ll*k*n/2; ++i)
	{
		auto cur=pq.top();
		res+=cur.fi;
		pq.pop();
		l[cur.se]--;
		r[cur.se]--;
		if(l[cur.se]==-1||r[cur.se]==m-k-1) continue;
		pq.push({1ll*(y[cur.se][l[cur.se]]+y[cur.se][r[cur.se]]),cur.se});
	}
	bool lst[n];
	memset(lst,0,sizeof lst);
	vector<pair<int,int>> a;
	vector<pair<int,int>> b;
	for (int i = 0; i < n; ++i)
	{
		int cnt=0;
		for (int j = 0; j <= l[i]; ++j)
		{
			a.pb({i,j});
		}
		for (int j = r[i]+1; j < m; ++j)
		{
			b.pb({i,j});
		}
	}
	int aa=0;
	int bb=0;
	for (int i = 0; i < k; ++i)
	{
		for (int j = 0; j < n/2; ++j)
		{
			ans[a[aa+j].fi][a[aa+j].se]=i;
		}
		for (int j = 0; j < n/2; ++j)
		{
			ans[b[bb+j].fi][b[bb+j].se]=i;
		}
		bb+=n/2;
		aa+=n/2;
	}
	allocate_tickets(ans);
	return res;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:52:7: warning: unused variable 'cnt' [-Wunused-variable]
   52 |   int cnt=0;
      |       ^~~

• 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