Cod sursa(job #2336573)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 5 februarie 2019 11:44:29
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

bool cmp(const pii &a, const pii &b)
{
    return a.second < b.second;
}

int main()
{
    ifstream in("heavymetal.in");
    int n;
    in >> n;
    vector<pii> v(n);
    for(auto &p:v)
        in >> p.first >> p.second;
    in.close();

    int rasp = 0;
    sort(v.begin(), v.end(), cmp);
    set<pii> dp; //.first = capat dreapta, .second = val
    for(auto &p:v)
    {
        int x = p.second - p.first;
        auto it = dp.upper_bound(make_pair(p.first, 0));
        if(it != dp.begin())
        {
            it--;
            x = max(x, x - (*it).second);
        }
        dp.insert(make_pair(p.second, -x));
        rasp = max(rasp, x);
    }

    ofstream out("heavymetal.out");
    out << rasp;
    out.close();
    return 0;
}