Cod sursa(job #461301)

Utilizator cont_de_testeCont Teste cont_de_teste Data 6 iunie 2010 11:53:44
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#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 i, cnt;
    //for (cnt = 1; cnt <= x; cnt <<= 1);

    for (i = 0, cnt = ( 1 << 20); 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;
}