Cod sursa(job #1898324)

Utilizator igroitaGroita Igor igroita Data 1 martie 2017 22:29:02
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<fstream>
#include<algorithm> 
using namespace std;
 
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
 
const int NMax = 1e5 + 5;
 
int Best[NMax];
pair < int, int > v[NMax];
 
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() {
 
    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)];
        Best[i] = max(Best[i], Best[i - 1]);
    }
 
    fout << Best[n];
 
    return 0;
}