Cod sursa(job #585909)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 30 aprilie 2011 12:37:37
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.56 kb
#include<stdio.h>
#include<algorithm>

using namespace std;

FILE*f=fopen("fabrica.in","r");
FILE*g=fopen("fabrica.out","w");

int n,na,nb,i,j,tmax,p,c,L,LHIP,tmax2;
int A[50005],B[50005],T[50005];

struct heap{
	int init;
	int crt;
}H[50005],HIP[50005],aux;

void urca(int x){
	
	c = x; p = x/2;
	
	while( p != 0 && H[p].crt > H[c].crt ){
		
		swap(H[p],H[c]);
		
		c = p; 
		p = p / 2;
	}
	
}

void coboara(int x){
	int y = 0;

	while (x != y)
	{
		y = x;
		if (y*2<=L && H[x].crt > H[2*y].crt) x = y*2;
		if (y*2+1<=L && H[x].crt > H[y*2+1].crt) x = y*2+1;
		swap(H[x],H[y]);
	}
}

void urcaHIP(int x){
	
	c = x; p = x/2;
	
	while( p != 0 && HIP[p].crt > HIP[c].crt ){
		
		swap(HIP[p],HIP[c]);
		
		c = p; 
		p = p / 2;
	}
	
}

void coboaraHIP(int x){
	int y = 0;

	while (x != y)
	{
		y = x;
		if (y*2<=LHIP && HIP[x].crt > HIP[2*y].crt) x = y*2;
		if (y*2+1<=LHIP && HIP[x].crt > HIP[y*2+1].crt) x = y*2+1;
		swap(HIP[x],HIP[y]);
	}
}

int main () {
	
	fscanf(f,"%d %d %d",&n,&na,&nb);
	
	for ( i = 1 ; i <= na ; ++i ){
		fscanf(f,"%d",&A[i]);
		aux.init = aux.crt = A[i];
		H[++L] = aux;
		urca(L);
	}
	for ( i = 1 ; i <= nb ; ++i ){
		fscanf(f,"%d",&B[i]);
		aux.init = B[i]; aux.crt = 0;
		HIP[++LHIP] = aux;
		urcaHIP(LHIP);
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		tmax = H[1].crt > tmax ? H[1].crt : tmax;
		tmax2 = H[1].crt + HIP[1].init > tmax2 ? H[1].crt + HIP[1].init : tmax2;
		
		HIP[1].crt = H[1].crt + HIP[1].init;
		H[1].crt = H[1].crt + H[1].init;
		
		coboara(1); coboaraHIP(1);
		
	}
	
	fprintf(g,"%d %d\n",tmax,tmax2);
	
	
	fclose(f);
	fclose(g);
	
	return 0;
}