Cod sursa(job #2336630)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 5 februarie 2019 12:58:36
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

bool cmp(const pii &a, const pii &b)
{
    if(a.second == b.second)
        return a.first < b.first;
    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();

    sort(v.begin(), v.end(), cmp);
    vector<int> dp(n);
    for(int i = 0; i < n; ++i)
    {
        int st = 0, dr = n, mid;
        int p = -1;
        while(st <= dr)
        {
            mid = (st + dr) / 2;
            if(v[mid].second <= v[i].first)
            {
                p = mid;
                st = mid + 1;
            }
            else
                dr = mid - 1;
        }
        if(i > 0)
            dp[i] = dp[i-1];
        dp[i] = max(dp[i], (p == -1 ? 0 : dp[p]) + v[i].second - v[i].first);
    }

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