제출 #1239790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239790		Muhammad_Aneeq	Carnival Tickets (IOI20_tickets)	C++17	14 / 100	387 ms	53328 KiB

tickets

#include "tickets.h"
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
#define ll long long
int const N=1510;
ll mul(ll a,ll b)
{
	return a*b;
}
long long find_maximum(int k, vector<vector<int>> a) {
	int n = a.size();
	int m = a[0].size();
	vector<pair<ll,int>>pq;
	vector<vector<int>>ret(n,vector<int>(m,-1));
	set<pair<int,int>>cnt;
	int l[n],r[n];
	ll ans=0;
	for (int i=0;i<n;i++)
	{
		l[i]=0,r[i]=m-1;
		int f=0;
		for (int j=0;j<m;j++)
			f+=(a[i][j]==0);
		cnt.insert({f,i});
	}
	for (int index=0;index<k;index++)
	{
		vector<int>g;
		vector<int>f;
		for (int i=0;i<n/2;i++)
		{
			g.push_back((*rbegin(cnt)).second);
			f.push_back((*rbegin(cnt)).first);
			cnt.erase(*rbegin(cnt));
		}
		int cn=0;
		for (auto i:g)
		{
			cn+=(a[i][l[i]]==0);
			ret[i][l[i]]=index;
			l[i]++;
		}
		for (auto [j,i]:cnt)
		{
			cn+=(a[i][r[i]]==0);
			ret[i][r[i]]=index;
			r[i]--;
		}
		ans+=min(n-cn,cn);
		for (int i=0;i<n/2;i++)
			cnt.insert({f[i]-1,g[i]});
	}
	allocate_tickets(ret);
	return ans;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 16
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10