Cod sursa(job #138351)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 18 februarie 2008 13:14:48
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<stdio.h>
long int n,i,a[100002],b[100002],max0,lh,h[100002],vh[100002],max,max1,aux;
void hd(long int ic,long int nc);
void sh(long int i1,long int i2);
void hd1(long int ic);
void hu(long int ic);
void sh1(long int i1,long int i2);

void insheap(long int poz,long int val);
int main()
{
	FILE *f,*g;f=fopen("heavymetal.in","r");g=fopen("heavymetal.out","w");
	fscanf(f,"%ld",&n);
	for(i=1;i<=n;i++){fscanf(f,"%ld%ld",&a[i],&b[i]);b[i]-=a[i];}
	for(i=n/2;i>=1;i--)hd(1,n);
	for(i=n;i>=1;i--){sh(1,i);hd(1,i-1);}
        lh=1;h[1]=a[1]-1;vh[1]=0;
	for(i=1;i<=n;i++)
	{ max0=0;
	  while(lh&&(a[i]>=h[1]))
	  { max0=(max0>=vh[1])?max0:vh[1];
	    h[1]=h[lh];vh[1]=vh[lh];lh--;hd1(1);
	  }
	  max1=max0+b[i];max=(max>=max1)?max:max1;
	  lh++;h[lh]=a[i];vh[lh]=max0;hu(lh);
	  lh++;h[lh]=a[i]+b[i];vh[lh]=max1;hu(lh);
	}
	fprintf(g,"%ld\n",max);
	fcloseall();return 0;
}
void hd(long int ic,long int nc)
{
	long int is,is1;
	is=2*ic;is1=is+1;
	if(is>nc)return;
	if(is<nc) if(a[is1]>a[is]) is=is1;
	if(a[is]>a[ic]){sh(is,ic);hd(is,nc);}
}
void sh(long int i1,long int i2)
{
	aux=a[i1];a[i1]=a[i2];a[i2]=aux;
	aux=b[i1];b[i1]=b[i2];b[i2]=aux;
}
void hd1(long int ic)
{
	long int is,is1;
	is=2*ic;is1=is+1;
	if(is>lh)return;
	if(is<lh) if(h[is1]<h[is]) is=is1;
	if(h[is]<h[ic]){sh1(is,ic);hd1(is);}
}
void sh1(long int i1,long int i2)
{
	aux=h[i1];h[i1]=h[i2];h[i2]=aux;
	aux=vh[i1];vh[i1]=vh[i2];vh[i2]=aux;
}
void hu(long int ic)
{
	long int is;
	is=ic/2;
	if(!is)return;
	if(h[is]>h[ic]){sh1(is,ic);hu(is);}
}