Cod sursa(job #2505593)

Utilizator CozminelDanielLupu Cosmin-Daniel CozminelDaniel Data 7 decembrie 2019 08:34:13
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

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

struct interval
{
    int st, dr;
    bool operator < (const interval A) const
    {
        return dr < A.dr;
    }
};

interval t[100003], dp[100003];
int n, k;

int CautareBinara(int x)
{
    int st, dr, p, mij;
    st = 0;
    dr = p = k;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(dp[mij].st <= x)
        {
            p = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return p;
}

int main()
{
    int x, y, p;
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> t[i].st >> t[i].dr;
    fin.close();
    sort(t + 1, t + n + 1);
    //for(int i = 1; i <= n; i++)
      //  fout << t[i].st << " " << t[i].dr << "\n";
    for(int i = 1; i <= n; i++)
    {
        x = t[i].st;
        y = t[i].dr;
        /// caut binar in dp cea mai din dreapta pozitie p cu dp[p].dr <= x
        p = CautareBinara(x);
        if(dp[k].st == y)
            dp[k].dr = max(dp[k].dr, dp[p].dr + y - x);
        else
        {
            k++;
            dp[k].st = y;
            dp[k].dr = max(dp[k - 1].dr, dp[p].dr + y - x);
        }
    }
    fout << dp[k].dr << "\n";
    fout.close();
    return 0;
}