Cod sursa(job #461400)

Utilizator SpiderManSimoiu Robert SpiderMan Data 6 iunie 2010 17:57:20
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#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;
}