Pagini recente » Cod sursa (job #1767147) | Cod sursa (job #2309892) | Cod sursa (job #1726952) | Cod sursa (job #1533749) | Cod sursa (job #871746)
Cod sursa(job #871746)
#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;
}