Cod sursa(job #249763)

Utilizator ConsstantinTabacu Raul Consstantin Data 29 ianuarie 2009 09:22:50
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<stdio.H>
int best[1000],m2,i,t,max,j,k,l,m,n;
struct concert {int x,y;} v[1000],norm[1000];
int sort(int i,int j){
concert aux;
int di=1,dj=0,au;
while(i<j)
	{if(v[i].y>v[j].y)
		{aux=v[i];
		v[i]=v[j];
		v[j]=aux;
		au=di;
		di=dj;
		dj=au;}
	i+=di;
	j-=dj;
	}
return i;}
void quick(int st,int dr)
	{int p;
	if(st<dr)
		{p=sort(st,dr);
		 quick(st,p-1);
		 quick(p+1,dr);

		}
	}

int caut(int val){
if(val<norm[1].y)return 0;
int p=1,u=i,mij;
while(p<=u)
	{mij=(p+u)>>1;
	if(norm[mij].y<val)
		p=mij+1;
	else
	if(norm[mij].y>val)
		u=mij-1;
	else
		return mij;
	}
return u;
}




int main(){
FILE *f=fopen("heavymetal.in","r");
fscanf(f,"%d",&n);


for(i=1;i<=n;i++)
	fscanf(f,"%d %d",&v[i].x,&v[i].y);
fclose(f);
quick(1,n);


for(i=1;i<=n;i++)
	if(v[i].y==v[i-1].y)
		norm[i]=norm[i-1];
	else
		{norm[i].x=norm[i-1].x+1;
		norm[i].y=v[i].y;}
k=1;
for(i=1;i<=n;i++)
	{t=caut(v[i].x);
	if(v[i].y!=v[i-1].x)
		k++;
	if(best[k]==0)
		best[k]=best[k-1];
	max=best[k];
	t=norm[t].x+1;
	m2=best[t];
	m2+=v[i].y;
	m2-=v[i].x;
	if(m2>max)
		best[k]=m2;
	}
FILE *g=fopen("heavymetal.out","w");
fprintf(g,"%d",best[k]);
fclose(g);
return 0;}