Cod sursa(job #2108754)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 18 ianuarie 2018 19:30:46
Problema Heavy metal Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 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<<17, 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 = 1; i <= n; ++i) {
        cin >> v[i].second >> v[i].first;
    }
    sort(v + 1, v + n + 1);
    for (int i = 1; i <= n; ++i) {
        d[i] = d[i - 1];
        x = cb(v[i].second);
        //cout << x << " " << i << "\n";
        d[i] = max(d[i], d[x] + v[i].first - v[i].second);
    }
    cout << d[n - 1];
    return 0;
}