Cod sursa(job #2122267)

Utilizator mariusn01Marius Nicoli mariusn01 Data 4 februarie 2018 20:24:05
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <algorithm>
#define st first
#define dr second

using namespace std;

pair<int, int> v[100010];
int D[100010];

int n, i, p, u, mid;

int cmp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int main () {
    ifstream fin ("heavymetal.in");
    ofstream fout("heavymetal.out");
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>v[i].st>>v[i].dr;
    }

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

    D[0] = 0;
    for (i=1;i<=n;i++) {
        /// caut cea mai mare valoare cu dr <= v[i].st

        D[i] = D[i-1];

        p = 0; u = i-1;
        while (p <= u) {
            int mid = (p+u)/2;

            if (v[mid].dr <= v[i].st)
                p = mid + 1;
            else
                u = mid - 1;
        }

        D[i] = max(D[i], D[u] + v[i].dr - v[i].st);

    }

    fout<<D[n];

    return 0;
}