Cod sursa(job #585875)

Utilizator cdascaluDascalu Cristian cdascalu Data 30 aprilie 2011 12:23:21
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 2.68 kb
#include<fstream>
#include<algorithm>
#define Nmax 100003
#define Nrmax 50003
#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
int heap[Nrmax],heaps[Nrmax];
inline int left_son(int x){return 2*x;}
inline int right_son(int x){return 2*x+1;}
inline int father(int x){return x/2;}
void sift(int x)
{
	int son,fiu1,fiu2,ind;
	do
	{
		son = 0;
		if(left_son(x)<=nra)
		{
			son = left_son(x);
			fiu1 = heap[left_son(x)];
			fiu2 = heap[right_son(x)];
			if(right_son(x)<=nra && ta[fiu1] + A[fiu1] > ta[fiu2] + A[fiu2])
				son = right_son(x);
		}
		ind = heap[x];
		if(ta[ind] + A[ind] <= ta[heap[son]] + A[heap[son]])
			son = 0;
		if(son)
		{
			heap[x] = heap[son];
			heap[son] = ind;
			x = son;
		}
	}while(son);
}
void percolate(int x)
{
	int aux;
	while(father(x) && ta[heap[father(x)]] + A[heap[father(x)]] > ta[heap[x]] + A[heap[x]])
	{
		aux = heap[father(x)];
		heap[father(x)] = heap[x];
		heap[x] = aux;
		x = father(x);
	}
}
void sifts(int x)
{
	int son,fiu1,fiu2,ind;
	do
	{
		son = 0;
		if(left_son(x)<=nrb)
		{
			son = left_son(x);
			fiu1 = heaps[left_son(x)];
			fiu2 = heaps[right_son(x)];
			if(right_son(x)<=nrb && tb[fiu1] + B[fiu1] > tb[fiu2] + B[fiu2])
				son = right_son(x);
		}
		ind = heaps[x];
		if(tb[ind] + B[ind] <= tb[heaps[son]] + B[heaps[son]])
			son = 0;
		if(son)
		{
			heaps[x] = heaps[son];
			heaps[son] = ind;
			x = son;
		}		
	}while(son);
}
void percolates(int x)
{
	int aux;
	while(father(x) && tb[heaps[father(x)]] + B[heaps[father(x)]] > tb[heaps[x]] + B[heaps[x]])
	{
		aux = heaps[father(x)];
		heaps[father(x)] = heaps[x];
		heaps[x] = aux;
		x = father(x);
	}
}
void read()
{
	ifstream f("fabrica.in");
	f>>N>>nra>>nrb;
	int i;
	for(i=1;i<=nra;++i)
	{
		f>>A[i];
		heap[i] = i;
		percolate(i);
	}
	for(i=1;i<=nrb;++i)
	{
		f>>B[i];
		heaps[i] = i;
		percolates(i);
	}
	f.close();
}
void firstp()
{
	int i,pr;
	for(i=1;i<=N;++i)
	{
		pr = heap[1];
		ta[pr] += A[pr];
		sift(1);
		doza[i] = ta[pr];
		if(doza[i]>maxim)
			maxim = doza[i];
	}
}
void secondp()
{
	int i,pr;
	for(i=1;i<=N;++i)
	{
		pr = 0;
		while(pr!=heaps[1])
		{
			pr = heaps[1];
			if(doza[i] > tb[pr])
			{
				tb[pr] = doza[i];			
				sifts(1);
			}
		}
		tb[pr] = max(tb[pr], doza[i]) + B[pr];
		sifts(1);
		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;
}