Pagini recente » Cod sursa (job #1598839) | Cod sursa (job #1033419) | Cod sursa (job #983400) | Cod sursa (job #959944) | Cod sursa (job #461307)
Cod sursa(job #461307)
#include <algorithm>
using namespace std;
#define DIM (1<<18)
struct punct {
int x, y;
};
int N, sol[ DIM ];
punct a[ DIM ];
inline int cmp( const punct &a, const punct &b ) {
return ( a.y < b.y ) || ( a.y == b.y && a.x < b.x );
}
inline int cautbin( int l, int r, int x ) {
int i, cnt;
for (cnt = 1; cnt < N; cnt <<= 1);
for (i = 0; cnt; cnt >>= 1)
if (i + cnt < N && a[i + cnt].y <= x)
i += cnt;
return i;
}
int main() {
freopen( "heavymetal.in", "r", stdin );
freopen( "heavymetal.out", "w", stdout );
int i;
scanf( "%d", &N );
for( i = 1; i <= N; ++i )
scanf( "%d %d", &a[ i ].x, &a[ i ].y );
sort( a+1, a+N+1, cmp );
sol[ 1 ] = a[ 1 ].y - a[ 1 ].x;
for( i = 2; i <= N; ++i ) {
sol[ i ] = sol[ i-1 ];
sol[ i ] = max( sol[ i ], sol[ cautbin( 1, i-1, a[ i ].x ) ] + a[ i ].y - a[ i ].x );
}
printf( "%d", sol[ N ] );
return 0;
}