Cod sursa(job #154316)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 11 martie 2008 09:23:51
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>
#include <stdlib.h>
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;
	if(aaa.b<bbb.b) return -1;
	return 0;
}
int main(){
	int n,i,best[1000000]={0},j,max=0,t=1;
	interval v[100005];
	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);
		if(v[i].b>max) max=v[i].b;
	}
	qsort(v,n+1,sizeof(v[0]),comp);
	for(i=1;i<=max;i++){
		best[i]=best[i-1];
		if(v[t].b==i) {
			for(j=1;v[j].b<=i;j++)
				if(best[i]<best[v[j].a]+(v[j].b-v[j].a)) best[i]=best[v[j].a]+(v[j].b-v[j].a);
			t++;
		}
	}
	printf("%d",best[max]);
	return 0;
}