Cod sursa(job #395332)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 12 februarie 2010 20:30:21
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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 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;
}