Cod sursa(job #585999)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 30 aprilie 2011 13:08:44
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 2.17 kb
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

#define N_MAX 50005
#define INF (1<<30)

int costa[N_MAX],costb[N_MAX];
int finish[N_MAX];
int finish2[N_MAX];
int dim[N_MAX];
bool ut[N_MAX];

set <int> S[N_MAX];

struct cmp
{
	bool operator () (const int a,const int b) const
	{
		return finish[a]+costa[a]>finish[b]+costa[b]||finish[a]+costa[a]==finish[b]+costa[b]&&costa[a]>costa[b];
	}
};

struct cmp2
{
	bool operator () (const int a,const int b) const
	{
		return finish2[a]+costb[a]>finish2[b]+costb[b]||finish2[a]+costb[a]==finish2[b]+costb[b]&&costb[a]>costb[b];
	}
};

struct cmp3
{
	bool operator () (const int a,const int b) const
	{
		return a>b;
	}
};

priority_queue <int,vector <int>,cmp> PQ1;
priority_queue <int,vector <int>,cmp2 > PQ2;

priority_queue <int,vector <int>,cmp3 > PQ3;

int n,nra,nrb,i,j;

int sol1,sol2;

int main()
{
	freopen("fabrica.in","r",stdin);
	freopen("fabrica.out","w",stdout);
	
	scanf("%d%d%d",&n,&nra,&nrb);
	
	for(i=1;i<=nra;i++)
		scanf("%d",&costa[i]);
	for(i=1;i<=nrb;i++)
		scanf("%d",&costb[i]);
	
	sort(costa+1,costa+nra+1);
	sort(costb+1,costb+nrb+1);
	
	int umplere=0,scoase=0;
	
	for(i=1;i<=nra;i++)
	{
		dim[i]=1;
		PQ1.push(i);
	}
	
	while(1)
	{
		if(umplere<n||scoase<n)
		{
			int nod=PQ1.top();
			if(dim[nod])
			{
				PQ1.pop();
				dim[nod]--;
				scoase+=ut[nod];
				if(ut[nod])
				{
					PQ3.push(finish[nod]);
				}
				ut[nod]=1;
			}
			if(scoase==n)
				break;
			if(umplere==n)
				continue;
			finish[nod]+=costa[nod];
			dim[nod]++;
			PQ1.push(nod);
			umplere++;
		}
		else
		{
			break;
		}
	}
	
	memset(dim,0,sizeof(dim));
	memset(ut,0,sizeof(ut));
	
	for(i=1;i<=nrb;i++)
	{
		dim[i]=1;
		PQ2.push(i);
	}
	
	while(!PQ3.empty())
	{
		int timp=PQ3.top();
		PQ3.pop();
		
		int nod=PQ2.top();
		if(dim[nod])
		{
			PQ2.pop();
			dim[nod]--;
		}
		finish2[nod]=max(finish2[nod],timp)+costb[nod];
		dim[nod]++;
		PQ2.push(nod);
	}
	
	for(i=1;i<=nra;i++)
		sol1=max(sol1,finish[i]);
	
	for(i=1;i<=nrb;i++)
		sol2=max(sol2,finish2[i]);
	
	printf("%d %d\n",sol1,sol2);
	
	return 0;
}