Pagini recente » Cod sursa (job #2518321) | Cod sursa (job #1659701) | Cod sursa (job #1128882) | Cod sursa (job #856310) | Cod sursa (job #395332)
Cod sursa(job #395332)
#include <algorithm>
using namespace std;
#define DIM (1<<17)
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, const int &x ) {
int m, poz;
poz = 0;
while( l <= r ) {
m = (l+r) / 2;
if( a[ m ].y <= x ) {
poz = m;
l = m+1;
}
else
r = m-1;
}
return poz;
}
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;
}