Cod sursa(job #1368473)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 2 martie 2015 17:52:49
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <algorithm>
#define MAXN 100000
#define LOG 17
using namespace std;

struct formatie{
    int A, B;
};

bool cmp(formatie x, formatie y) {
    if (x.B < y.B || (x.B == y.B && x.A < y.A))
        return true;
    return false;
}
formatie v[MAXN + 1];
int D[MAXN + 1];

int bsearch(int right, int val) {
    int p = 0, pas = (1 << LOG);
    while (pas) {
        int pos = p + pas;
        if (pos <= right && v[pos].B <= val)
            p = pos;
        pas >>= 1;
    }

    if (v[p].B > val)
        return -1;
    return p;
}

int main () {
    ifstream cin("heavymetal.in");
    ofstream cout("heavymetal.out");

    int n;
    cin >> n;
    for (int i = 0 ; i < n ; ++i)
        cin >> v[i].A >> v[i].B;

    sort(v, v + n, cmp);

    D[0] = v[0].B - v[0].A;
    for (int i = 1 ; i < n ; ++i) {
        int p = bsearch(i - 1, v[i].A);
        if (p == -1)
            D[i] = 1;
        else
            D[i] = (v[i].B - v[i].A) + D[p];

        if (D[i] < D[i - 1])
            D[i] = D[i - 1];
    }

    cout << D[n - 1];
    return 0;
}