Cod sursa(job #720692)

Utilizator danalex97Dan H Alexandru danalex97 Data 22 martie 2012 20:30:53
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define InFile "fabrica.in"
#define OutFile "fabrica.out"

#define NrAmax 50011
#define NrBmax 50011
#define Nmax 100011
#define max(a, b) ( ( a>b ) ? a : b )
#define min(a, b) ( ( a<b ) ? a : b )

int N,NrA,NrB;
int V_A[NrAmax];
int T_A[NrAmax];
int V_B[NrBmax];
int T_B[NrBmax];
int MaxA,MaxB;
int Time[Nmax];

void Down(int n,int k,int V[],int T[],char inF)
{
	if (inF=='V')
	{
		int p;
		p=1;
		while (p)
		{
			p=0;
			if (2*k<=n) 
			{
				p=2*k; 
				if ( (2*k+1<=n) && (V[2*k+1]<V[2*k]) ) 
					p++; 
				if (V[p] >= V[k])
					p=0;
			}
			if (p)  
			{
				swap(V[k],V[p]); 
				swap(T[k],T[p]); 
				k=p;
			}
		}
	}
	else
	{
		int p;
		p=1;
		while (p)
		{
			p=0;
			if (2*k<=n) 
			{
				p=2*k; 
				if ( (2*k+1<=n) && (T[2*k+1]+V[2*k+1]<T[2*k]+V[2*k]) ) 
					p++; 
				if (T[p]+V[p] >= T[k]+V[k])
					p=0;
			}
			if (p)  
			{
				swap(T[k],T[p]); 
				swap(V[k],V[p]); 
				k=p;
			}
		}
	}
}

void Up(int co,int i,int V[],int T[],char inF)
{
	if (inF=='V')
		while (V[i]<V[i/2] && i/2>0) 
		{
			swap(V[i],V[i/2]);
			swap(T[i],T[i/2]);
			i=i/2;
		}
	else
		while (T[i]<T[i/2] && i/2>0) 
		{
			swap(T[i],T[i/2]);
			swap(V[i],V[i/2]);
			i=i/2;
		}
}

void insert(int i,int x,int y,int V[],int T[])
{
	V[i]=x;
	T[i]=y;
	Up(i,i,V,T,'V');
}

int main()
{
	freopen(InFile,"r",stdin);
	freopen(OutFile,"w",stdout);
	
	scanf("%d%d%d",&N,&NrA,&NrB);
	
	for (int i=1;i<=NrA;++i)
		scanf("%d",&V_A[i]);
	for (int i=1;i<=NrB;++i)
		scanf("%d",&V_B[i]);
	sort(V_A,V_A+NrA+1);
	sort(V_B,V_B+NrB+1);
	
	for (int i=1;i<=N;++i)
	{
		T_A[1]+=V_A[1];
		Down(NrA,1,V_A,T_A,'T');
		Time[i]=T_A[1];
	}
	
	for (int i=1;i<=N;++i)
	{
		T_B[1]=max(Time[i],T_B[1]);
		T_B[1]+=V_B[1];
		Down(NrB,1,V_B,T_B,'T');
	}
	
	for (int i=1;i<=NrA;++i)
		MaxA=max(T_A[i],MaxA);
	for (int i=1;i<=NrB;++i)
		MaxB=max(T_B[i],MaxB);
	
	printf("%d %d\n",MaxA,MaxB);
	
	return 0;
}