Cod sursa(job #731316)

Utilizator vendettaSalajan Razvan vendetta Data 7 aprilie 2012 21:29:39
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <algorithm>
#define nmax 100005

using namespace std;

int n, d[nmax];
pair<int,int> v[nmax];

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

bool cmp(pair<int,int> a, pair<int,int> b){

    return a.second < b.second;

}

void citeste(){

    f >> n;

    for(int i=1; i<=n; i++){
        int x,y;
        f >> x >> y;
        v[i]=(make_pair(x, y));
    }

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

}

int cb(int val){

    int st=1;
    int dr=n;
    int rez = 0;

    while(st <= dr){
        int mij = (st + dr) / 2;
        if (v[mij].second <= val){
            rez = mij;
            st = mij+1;
        }else dr = mij-1;
    }

    return rez;

}

void rezolva(){

    d[0] = 0;

    for(int i=1; i<=n; i++){
        int start = v[i].first;
        int final = v[i].second;
        int poz = cb(start);
        d[i] = max(d[i-1], d[poz] + (final - start));
    }

    g << d[n] << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}