Cod sursa(job #2049878)

Utilizator CammieCamelia Lazar Cammie Data 27 octombrie 2017 19:12:09
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda hlo2017_cj_av_l4 Marime 1.18 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define MAXN 100002

using namespace std;

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

struct str{
    int A, B;

    bool operator < (const str& other) const{
        if (B == other.B)
            return A < other.A;
        return B < other.B;
    }
};

vector <str> C;

int n, best[MAXN];

inline void Read() {
    int a, b;

    fin >> n;

    for (int i = 0; i < n; i++) {
        fin >> a >> b;

        C.push_back({a, b});
    }

    sort(C.begin(), C.end());
}

inline int search_(int N) {
    int ii, step;

    for (step = 1; step < N - 1; step <<= 1);

    for (ii = 0; step; step >>= 1){
        if (ii + step <= N - 1 && C[ii + step - 1].B <= C[N - 1].A)
            ii += step;
    }
    return ii;
}

inline void DP() {
    best[1] = C[0].B - C[0].A;
    int poz;

    for (int i = 2; i <= n; i++) {
        best[i] = best[i - 1];
        poz = search_(i);
        best[i] = max(best[i - 1], best[poz] + C[i - 1].B - C[i - 1].A);
    }

    fout << best[n];
}

int main () {
    Read();
    DP();

    fin.close(); fout.close(); return 0;
}