Pagini recente » Cod sursa (job #3288423) | Cod sursa (job #2475153) | Cod sursa (job #3259028) | Cod sursa (job #636420) | Cod sursa (job #3224275)
#include<bits/stdc++.h>
#define int long long
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int n,d[100001],mx=-1;
struct form {
int x,y;
}v[100001];
bool comp(form a, form b) {
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
int32_t main()
{in>>n;
for(int i=1;i<=n;++i)
in>>v[i].x>>v[i].y;
sort(v+1,v+n+1,comp);
d[1]=v[1].y-v[1].x;
for(int i=2;i<=n;++i) {
int st=1,dr=i,sol=0;
while(st<=dr) {
int mij=(st+dr)/2;
if(v[mij].y<=v[i].x) st=mij+1,sol=mij;
else dr=mij-1;
}
d[i]=max(d[i-1],v[i].y-v[i].x+d[sol]);
}
out<<d[n];
return 0;
}