Cod sursa(job #1335855)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 5 februarie 2015 23:15:46
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <algorithm>
#define DIM 100010
#define l first
#define r second
using namespace std;

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

long long n, m, i, j, k, ok, minim, aux, best[DIM];
pair <int , int > v[DIM]; long long a, b, mid;

long long max(long long a, long long b){
    if(a > b)
        return a;
    else
        return b;
}

void SetUpNormal(){
    fin >> n;
    for(i = 1; i <= n; i ++)
        fin >> v[i].r >> v[i].l;
    sort(v + 1, v + n + 1);
    for(i = 1; i <= n; i ++){
        aux = v[i].l;
        v[i].l = v[i].r;
        v[i].r = aux;
    }
    return;
}

void DinamycGredy(){
    best[1] = v[1].r - v[1].l;
    for(i = 2; i <= n; i ++){
        best[i] = best[i-1];
        best[i] = max(best[i], v[i].r - v[i].l);
        a = 1; b = i-1;
        while(a <= b){
            mid = (a+b) / 2;
            if(v[mid].r <= v[i].l)
                a = mid + 1;
            else
                b = mid - 1;
        }
        best[i] = max(best[i], best[b] + v[i].r - v[i].l);
    }
    fout << best[n];
    return;
}

int main(){
    SetUpNormal();
    DinamycGredy();
    return 0;
}