Cod sursa(job #871746)

Utilizator stefan.friptuPetru Stefan Friptu stefan.friptu Data 5 februarie 2013 09:54:56
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>
#include <algorithm>

using namespace std;
   
int val,u,mij,sol,v[100001],n,i,k,c,p;   
   
struct HEAVY {
	
	long a;
	long b;
};	


int cmp(HEAVY a,HEAVY b){
	return a.b<b.b;
}

HEAVY s[100001],aux;

int main(){   
   
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	
	scanf("%ld",&n);   
	
	for(i=1;i<=n;i++){   
		scanf("%d%d",&s[i].a,&s[i].b);   
	}   
	sort(s+1,s+n+1,cmp);
	
    for(i=1;i<=n;i++){   
		val=s[i].a;   
		v[i]=v[i-1];   
		p=0;   
		u=i;   
		while(p<=u){   
			mij=(p+u)/2;   
		if(s[mij].b<=val)   
			p=mij+1;   
		else 
		    u=mij-1;
		}   
	if((v[u]+(s[i].b-s[i].a))>v[i])   
		v[i]=v[u]+(s[i].b-s[i].a);   
	}   
	printf("%ld\n",v[n]);
	
	return 0;   
}