Cod sursa(job #2511585)

Utilizator alexnigaNiga Alexandru alexniga Data 19 decembrie 2019 13:02:45
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

struct interv
{
    int x, y;
};

int cmp(interv a, interv b)
{
    if (a.y != b.y)
        return a.y < b.y;
    return a.x < b.x;
}

int cautBin(int st, int dr, int maxx, vector <interv> &v)
{
    int answ = 0;

    while(st <= dr)
    {
        int mij = (st + dr) / 2;

        if (v[mij].y <= maxx)
            {
                answ = mij;
                st = mij + 1;
            }
        else
            dr = mij - 1;
    }

    return answ;
}

int main()
{
    int n;

    f >> n;

    vector <interv> v(n + 1);
    vector <int> dp(n + 2, 0);

    for (int i = 0; i < n; i++)
        f >> v[i].x >> v[i].y;
    v[n].x = -1;
    v[n].y = -1;

    sort(v.begin(), v.begin() + n + 1, cmp);

    // for (int i = 0; i <= n; i++)
    //    cout << v[i].x << " " << v[i].y << "\n";
    //cout << "\n";
    dp[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        int xi = v[i].x;
        int yi = v[i].y;

        int j = cautBin(0, n, xi, v);

//        cout << xi << " " << yi << " " << j << "\n";
        dp[i] = max(dp[i - 1], yi - xi + dp[j]);
    }

    g << dp[n];

    return 0;
}