Cod sursa(job #1894984)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 27 februarie 2017 18:27:43
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 1e5 + 5;

int Best[NMax];
pair < int, int > v[NMax];

inline int Binary(int hi, const int &value) {
    int lo = 1;
    int best = 0;
    while(lo <= hi) {
        int mid = (lo + hi) >> 1;

        if(v[mid].first > value) {
            hi = mid - 1;
        } else {
            best = mid;
            lo = mid + 1;
        }
    }

    return best;
}

int main() {
    ios::sync_with_stdio(false);

    int n;
    fin >> n;

    v[0] = {-1, -1};
    for(int i = 1; i <= n; i++) fin >> v[i].second >> v[i].first;

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

    for(int i = 1; i <= n; i++) {
        Best[i] = v[i].first - v[i].second + Best[Binary(i - 1, v[i].second)];
    }

    fout << Best[n];

    return 0;
}