Cod sursa(job #1851963)

Utilizator VasilescuVasilescu Eliza Vasilescu Data 20 ianuarie 2017 12:57:31
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
# 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() {
    FILE *fin, *fout;
    fin=fopen("heavymetal.in", "r");
    fout=fopen("heavymetal.out", "w");
    int n;
    fscanf(fin, "%d", &n);

    for ( int i = 1; i <= n; i ++ )
       fscanf(fin, "%d%d", &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 ) );
    }

    fprintf(fout, "%d\n", d[n]);


    return 0;
}