Cod sursa(job #177621)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 13 aprilie 2008 13:21:53
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>
#include <stdlib.h>
#define INF 2000000000
#define N 100005
struct interval{
	int a,b;
};
/*int comp(const void*a,const void*b){
	interval *aa=(interval*)a,*bb=(interval*)b;
	interval aaa=*aa,bbb=*bb;
	if(aaa.b<bbb.b) return -1;
	else if(aaa.b==bbb.b && aaa.a<bbb.a) return -1;
	if(aaa.b>bbb.b) return 1;
	return 0;
}*/
int maxim(int x, int y){
	if(x>y) return x;
	return y;
}
interval v[N];
int n;
void sortare(){
	int i,j,inj=n,gata,aux;
	while(inj>1){
		inj/=2;
		do{
			gata=1;
			for(i=1;i<=n-inj;i++)
				if(v[i].b>v[i+inj].b){
					aux=v[i].b;
					v[i].b=v[i+inj].b;
					v[i+inj].b=aux;
					aux=v[i].a;
					v[i].a=v[i+inj].a;
					v[i+inj].a=aux;
					gata=0;
				}
		}
		while(!gata);
	}
}
int main(){
	int i,best[N]={0},j,max=0;
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	scanf("%d",&n);
	v[0].a=0;v[0].b=0;
	for(i=1;i<=n;i++)
		scanf("%d%d",&v[i].a,&v[i].b);
	v[n+1].b=INF;
	sortare();
	//qsort(v,n+1,sizeof(v[0]),comp);
	/*for(i=1;i<=n;i++){
		max=0;
		best[v[i].b]=best[v[i-1].b];
			for(j=i-1;j>=1 && !max;j--)
				if(v[j].b<=v[i].a)max=maxim(max,best[v[j].b]);
		best[v[i].b]=maxim(max+v[i].b-v[i].a,best[v[i].b]);
	}*/
	printf("%d",best[v[n].b]);
	return 0;
}