Pagini recente » Borderou de evaluare (job #1991690) | Borderou de evaluare (job #636718) | Borderou de evaluare (job #1328869) | Borderou de evaluare (job #1525978) | Cod sursa (job #2412498)
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct COSTIN {
long long st,dr;
}v[100001];
long long d[100001];
bool cmp( COSTIN a, COSTIN b ) {
if( a.dr == b.dr )
return a.st < b.st;
return a.dr < b.dr;
}
int bs( int x ) {
int l,r,mid,last = 1;
l = 1;
r = x - 1;
while( l <= r ) {
mid = ( l + r ) / 2;
if( v[mid].dr <= v[x].st ) {
l = mid + 1;
last = mid;
}
else
r = mid - 1;
}
return last;
}
int main() {
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int i,j;
scanf("%d",&n);
for( i = 1; i <= n; i ++ ) {
scanf("%lld%lld",&v[i].st,&v[i].dr);
}
sort( v + 1, v + n + 1, cmp );
long long m = 0;
d[0] = v[0].dr - v[0].st;
for( i = 1; i <= n; i ++ ) {
j = bs(i);
d[i] = max( d[i-1],d[j]+(v[i].dr-v[i].st));
if( m < d[i] )
m = d[i];
}
printf("%lld",m);
return 0;
}