Pagini recente » Cod sursa (job #242904) | Cod sursa (job #1047170) | Cod sursa (job #2089872) | Cod sursa (job #3138247) | Cod sursa (job #177652)
Cod sursa(job #177652)
#include <stdio.h>
#include <stdlib.h>
#define INF 2000000000
#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;
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 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,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);
sortare();
for(i=1;i<=n;i++){
best[v[i].b]=best[v[i-1].b];
max=caut(1,i-1,v[i].a);
best[v[i].b]=maxim(best[v[max].b]+v[i].b-v[i].a,best[v[i].b]);
}
printf("%d",best[v[n].b]);
return 0;
}