Cod sursa(job #178142)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 14 aprilie 2008 09:32:21
Problema Heavy metal Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#include <stdlib.h>
#define N 100005
struct interval{
	int a,b;
};
int maxim(int x, int y){
	if(x>y) return x;
	return y;
}
interval v[N];
int n,best[N];
void sortare(){
	int i,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 || (v[i].b==v[i+inj].b && v[i].a<v[i+inj].a)){
					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 caut(int st,int dr,int x){
	int m;
	while(st<=dr){
		m=(st+dr)/2;
		if(v[m].b==x) return m;
		if(v[m].b>x) dr=m-1;
		else st=m+1;
	}
	return st-1;
}
int main(){
	int i,max=0,poz;
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d%d",&v[i].a,&v[i].b);
	sortare();
	for(i=1;i<=n;i++){
		poz=caut(1,i-1,v[i].a);
		best[i]=maxim(best[poz]+v[i].b-v[i].a,best[i-1]);
		if(best[i]>max) max=best[i];
	}
	/*for(i=1;i<=n;i++)
		printf("%d ",v[i].b);
	printf("\n");
	for(i=1;i<=n;i++)
		printf("%d ",best[i]);*/
	printf("%d",max);
	return 0;
}