Cod sursa(job #340526)

Utilizator ZethpixZethpix Zethpix Data 15 august 2009 11:01:37
Problema Heavy metal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
long a[100002],b[100002],d[100002],i,n,j;
void inter(long x,long m,long y){
	long c[100002],d[100002];
	for(i=x;i<=y;i++){
		c[i]=a[i];
		d[i]=b[i];
	}
	long i1=x;
	long i2=m+1;
	long k=x-1;
	while(i1<=m&&i2<=y)
		if(d[i1]<d[i2]){
			a[++k]=c[i1++];
			b[k]=d[i1-1];
		}
		else{
			a[++k]=c[i2++];
			b[k]=d[i2-1];
		}
	for(i=i1;i<=m;i++){
		a[++k]=c[i];
		b[k]=d[i];
	}
	for(i=i2;i<=y;i++){ 
		a[++k]=c[i];
		b[k]=d[i];
	}
}
void sort(long x,long y){
	if(x!=y){
		long m=(x+y)/2;
		sort(x,m);
		sort(m+1,y);
		inter(x,m,y);
	}
}
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]);
	sort(1,n);
	d[1]=b[1]-a[1];
	for(i=2;i<=n;i++){
		d[i]=d[i-1];
		for(j=1;j<=n;j++)
			if(b[j]>a[i]) break;
		j--;
		if(d[i]<b[i]-a[i]+d[j])
			d[i]=b[i]-a[i]+d[j];
	}
	fprintf(g,"%ld\n",d[n]);
	fclose(f);
	fclose(g);
	return 0;
}