Pagini recente » Cod sursa (job #2976280) | Cod sursa (job #1412156) | Cod sursa (job #500613) | Cod sursa (job #2066590) | Cod sursa (job #1857601)
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
struct interval{int a,b,l;};
interval v[100001];
set <int> s;
set <int>::iterator it;
int d[200001];
bool cmp(interval x,interval y){
if(x.b<y.b)
return true;
else
return false;
}
int main(){
int n,i,k,kk;
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);
v[i].l=v[i].b-v[i].a;
s.insert(v[i].a);
s.insert(v[i].b);
}
for(i=1;i<=n;i++){
v[i].a=distance(s.begin(),s.find(v[i].a))+1;
v[i].b=distance(s.begin(),s.find(v[i].b))+1;
}
sort(v+1,v+n+1,cmp);
k=1;
it=s.end();
it--;
for(i=1;i<=s.size();i++){
d[i]=d[i-1];
while(v[k].b<i&&k<=n)
k++;
kk=k;
while(v[kk].b==i){
if(d[v[kk].a]+v[kk].l>d[i])
d[i]=d[v[kk].a]+v[kk].l;
kk++;
}
}
printf("%d",d[s.size()]);
return 0;
}