Cod sursa(job #922558)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 22 martie 2013 14:29:58
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 100001

struct VECTOR{

    int st;
    int dr;
    int val;
};

int N;
int B[Nmax];
VECTOR V[Nmax];

void citire(){

    freopen("heavymetal.in", "r", stdin);

    scanf("%d", &N);

    for ( int i = 1; i <= N; i++ )
        scanf("%d %d", &V[i].st, &V[i].dr),
        V[i].val = V[i].dr - V[i].st;

    fclose(stdin);
}

int cmp(VECTOR a, VECTOR b){

    return a.dr < b.dr;
}

int cautare (int left, int right, int x ) {

    int pos = 0;

    while ( left <= right ) {

        int mid = ( left + right ) / 2;

        if ( V[mid].dr <= x )
            left = mid + 1,
            pos = mid;
        else
            right = mid - 1;
        }

    return pos;
}
void rezolva() {

    for ( int i = 1; i <= N; ++i ) {

        int x = cautare ( 1, i - 1, V[i].st );

        B[i] = max(  B[i - 1], B[x] + V[i].val );
    }
}

void afis(){

    freopen("heavymetal.out", "w", stdout);

    printf("%d\n", B[N] );

    fclose(stdout);
}

int main(){

    citire();
    sort ( V + 1, V + N + 1, cmp );
    rezolva();
    afis();

    return 0;
}