Cod sursa(job #1851950)

Utilizator Teod12ALEXANDRESCU teodora Teod12 Data 20 ianuarie 2017 12:45:14
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
# include <iostream>
# include <fstream>

# include <algorithm>

using namespace std;

const int MAX_N = 100000;

struct interval{
    int b, e;
    bool operator<( const interval t ) const { return e < t.e; }
} v[1 + MAX_N + 1];
int d[1 + MAX_N];

int cbin( int t, int n ) {
    int i = 0;
    for ( int pas = ( 1 << 20 ); pas > 0; pas >>= 1 )
        if ( i + pas <= n && v[i + pas].e <= t )
            i += pas;
    return i;
}

int main() {
    ifstream fin( "heavymetal.in" );
    ofstream fout( "heavymetal.out" );

    int n;
    fin >> n;

    for ( int i = 1; i <= n; i ++ )
        fin >> v[i].b >> v[i].e;

    sort( v + 1, v + n + 1 );

    for ( int i = 1; i <= n; i ++ ) {
        int p = cbin( v[i].b, n );
        d[i] = max( d[i - 1], d[p] + ( v[i].e - v[i].b ) );
    }

    fout << d[n];

    fin.close();
    fout.close();

    return 0;
}