Cod sursa(job #2764897)

Utilizator emma.vasiiEmma Vasii emma.vasii Data 23 iulie 2021 11:53:58
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
//infoarema_Heavymetal
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
struct band {int lf, rg;};

ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");

int n, Optim[100002];
band B[100002];

int comparison (band x, band y)
{
    if (x.rg < y.rg)
        return 1;

    return 0;
}

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++)
        fin >> B[i].lf >> B[i].rg;

    sort (B + 1, B + n + 1, comparison);

    B[0].lf = B[0].rg = -1;
    Optim[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        Optim[i] = Optim[i - 1];

        int Left = 0, Right = i - 1;

        while(Left != Right)
        {
            int m = (Left + Right + 1) / 2;

            if (B[i].lf >= B[m].rg)
                Left = m;
            else
                Right = m - 1;
        }

        if ((B[i].rg - B[i].lf + Optim[Left]) > Optim[i])
            Optim[i] = B[i].rg - B[i].lf + Optim[Left];
    }

    fout << Optim[n];

    fin.close();
    fout.close();

    return 0;
}