Cod sursa(job #2108735)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 18 ianuarie 2018 19:17:47
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

int n;

pair < int, int > v[100010];

int d[100010];

int cb(int val) {
    int pas = 1<<16, r = 0;
    while (pas > 0) {
        if (pas + r < n && v[r + pas].first <= val) {
            r += pas;
        }
        pas /= 2;
    }
    return r;
}

int main()
{
    int x;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> v[i].second >> v[i].first;
    }
    sort(v, v + n);
    for (int i = 0; i < n; ++i) {
        d[i] = d[i - 1];
        x = cb(v[i].second);
        d[i] = max(d[i], d[x] + v[i].first - v[i].second);
    }
    cout << d[n - 1];
    return 0;
}