Pagini recente » Cod sursa (job #391788) | Cod sursa (job #945558) | Cod sursa (job #2124637) | Cod sursa (job #2322358) | Cod sursa (job #2412517)
#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 pas = 1<<20;
int r = 0;
while( pas > 0 ) {
pas /= 2;
if( r + pas < x && v[r+pas].dr <= v[x].st )
r += pas;
}
return r;
}
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] = 0;
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;
}