Pagini recente » Cod sursa (job #564550) | Cod sursa (job #1423757) | Cod sursa (job #618091) | Cod sursa (job #1247668) | Cod sursa (job #2866183)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,i,st,dr,mid,maxi,d[100001];
struct interval {
int x,y;
}v[100001];
bool cmp(interval a,interval b) {
return a.y<=b.y;
}
int main() {
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
d[0]=0;
for (i=1;i<=n;i++) {
d[i]=max(d[i-1],v[i].y-v[i].x);
st=1;
dr=i-1;
while (st<=dr) {
mid=(st+dr)/2;
if (v[i].x>=v[mid].y)
st=mid+1;
else
dr=mid-1;
}
d[i]=max(d[i],d[dr]+v[i].y-v[i].x);
if (d[i]>maxi)
maxi=d[i];
}
fout<<maxi;
return 0;
}