Cod sursa(job #585860)

Utilizator cdascaluDascalu Cristian cdascalu Data 30 aprilie 2011 12:18:18
Problema Fabrica Scor 12
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.38 kb
#include<fstream>
#include<algorithm>
#define Nmax 100001
#define Nrmax 50001
#define INF 0x3f3f3f3f
using namespace std;
int A[Nrmax],B[Nrmax],N,nra,nrb,ta[Nrmax],doza[Nmax],maxim,tb[Nrmax],Maxim;
//doza[i] timpul in care este terminata doza i
//ta[i] timpul in care termina toata treaba procesul i
void read()
{
	ifstream f("fabrica.in");
	f>>N>>nra>>nrb;
	int i;
	for(i=1;i<=nra;++i)
		f>>A[i];
	for(i=1;i<=nrb;++i)
		f>>B[i];
	f.close();
}
int detmin()
{
	int i,minim=INF,minP;
	for(i=1;i<=nra;++i)
	{
		if(ta[i]+A[i] < minim)
		{
			minim = ta[i]+A[i];
			minP = i;
		}
		if(!ta[i])i = nra;
	}
	return minP;
}
void firstp()
{
	sort(A+1,A+nra+1);
	int i,pr;
	for(i=1;i<=N;++i)
	{
		pr = detmin();
		ta[pr] += A[pr];
		doza[i] = ta[pr];
		if(doza[i]>maxim)
			maxim = doza[i];
	}
}
int detmins(int st)
{
	int i,minim=INF,minP;
	for(i=1;i<=nrb;++i)
	{
		if(max(tb[i],st) + B[i] < minim)
		{
			minim = max(tb[i],st) + B[i];
			minP = i;
		}
		if(!tb[i])i=nrb;
	}
	return minP;
}
void secondp()
{
	sort(B+1,B+nrb+1);
	sort(doza+1,doza+N+1);
	int i,pr;
	for(i=1;i<=N;++i)
	{
		pr = detmins(doza[i]);
		tb[pr] = max(tb[pr], doza[i]) + B[pr];
		doza[i] = tb[pr];
		if(doza[i]>Maxim)
			Maxim = doza[i];
	}
}
int main()
{
	read();
	firstp();
	secondp();
	ofstream g("fabrica.out");
	g<<maxim<<" "<<Maxim<<"\n";
	g.close();
	return 0;
}