Cod sursa(job #1752692)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 4 septembrie 2016 20:17:15
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <algorithm>
#define f first
#define s second
using namespace std;
long long n,i,best[100001],p,u,m,aux;
pair <long long,long long> v[100001];
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");

int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].s>>v[i].f;
    sort (v+1,v+n+1);
    for (i=1;i<=n;i++){
        aux = v[i].f;
        v[i].f = v[i].s;
        v[i].s = aux;
    }
    best[1] = v[1].s-v[1].f;
    for (i=2;i<=n;i++){
        best[i] = best[i-1];
        best[i] = max (best[i],v[i].s - v[i].f);
        p = 1;
        u = i-1;
        while (p<=u){
            m = (p+u)/2;
            if (v[m].s <= v[i].f)
                p = m+1;
            else
                u = m-1;
        }
        best[i] = max (best[i],best[u]+v[i].s-v[i].f);
    }
    // rezultatul ramane in best [n];
    fout<<best[n];

    return 0;
}