Pagini recente » Cod sursa (job #1411393) | Cod sursa (job #1380471) | Cod sursa (job #1675904) | Cod sursa (job #618862) | Cod sursa (job #461400)
Cod sursa(job #461400)
#include <algorithm>
using namespace std;
const char FIN[] = "heavymetal.in", FOU[] = "heavymetal.out";
const int MAX = 100005;
struct vec
{
int i, j;
};
int N, S[ MAX ];
vec V[ MAX ];
bool operator <( const vec &lhs, const vec &rhs )
{
if ( lhs.j == rhs.j ) return lhs.i < rhs.i;
return lhs.j < rhs.j;
}
inline int bin_search ( int val )
{
int i, cnt;
for (cnt = 1; cnt < N; cnt <<= 1);
for (i = 0; cnt; cnt >>= 1)
if (i + cnt < N && V[i + cnt].j <= val)
i += cnt;
return i;
}
int main()
{
freopen ( FIN , "r" , stdin );
freopen ( FOU , "w" , stdout );
int i;
scanf( "%d", &N );
for ( i = 1; i <= N; ++i )
scanf( "%d %d", &V[ i ].i, &V[ i ].j );
sort( V + 1 , V + N + 1 );
S[ 1 ] = V[ 1 ].j - V[ 1 ].i;
for ( i = 2; i <= N; ++i )
S[ i ] = max( S[ i - 1 ], S[ bin_search( V[ i ].i ) ] + V[ i ].j - V[ i ].i );
printf( "%d", S[ N ] );
return 0;
}