Pagini recente » Cod sursa (job #2593637) | Cod sursa (job #1402248) | Cod sursa (job #1335473) | Cod sursa (job #1901809) | Cod sursa (job #1692204)
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 100000;
struct Metal {
int x,y;
Metal() {}
Metal(int a,int b) {
x=a,y=b;
}
bool operator< (const Metal &other) const {
return y < other.y;
}
};
Metal v[NMAX + 5];
int d[NMAX + 5];
int main() {
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,maxim = -1;
scanf("%d",&n);
for(int i=1; i<=n; i++) {
int x,y;
scanf("%d%d",&x,&y);
v[i]=Metal(x,y);
}
sort(v+1,v+n+1);
for(int i=1; i<=n; i++) {
if ( v[i].x>v[1].y ) {
int st=1,dr=i;
while(st<=dr) {
int med=(st + dr)/2;
if(v[med].y <= v[i].x)
st=med+1;
else
dr=med-1;
}
int med=(st + dr)/2;
if(v[med].y>v[i].x)
med--;
d[i]=max(d[med]+v[i].y-v[i].x, maxim);
} else
d[i]=max( v[i].y-v[i].x, maxim );
if(d[i]>maxim)
maxim=d[i];
}
printf("%d\n",maxim);
}