Cod sursa(job #2521331)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 10 ianuarie 2020 19:16:13
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

#define N 100100

pair <long long, long long> v[N];
long long d[N], maxim[N];

int i, n, poz;

int bs (long long x){
    if (x < v[0].first)
        return -1;
    int ans = 0;
    for (int it = n; it > 0; it >>= 1)
        while (it + ans < n && x >= v[it + ans].first)
        ans += it;
    return ans;
}
int main()
{
    ifstream fin ("heavymetal.in");
    ofstream fout ("heavymetal.out");
    fin >> n;
    for (i = 0; i < n; ++i)
        fin >> v[i].second >> v[i].first;
    sort (v, v + n);
    d[0] = v[0].first - v[0].second;
    maxim[0] = d[0];
    for (i = 1; i < n; ++i){
        poz = bs (v[i].second);
        d[i] = v[i].first - v[i].second;
        if (poz > -1)
            d[i] += maxim[poz];
        maxim[i] = max (d[i], maxim[i - 1]);
    }
    fout << maxim[n - 1];
    return 0;
}