Cod sursa(job #2505595)

Utilizator ParutixLungeanu Razvan Parutix Data 7 decembrie 2019 08:34:23
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Interval
{
    int a, b;
    bool operator < (const Interval A) const
    {
        return b < A.b;
    }
};

Interval t[100005];
Interval dp[100005];
int n, k, x, y;

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

int main()
{
    int i, p;
    fin >> n;
    for(i = 1 ; i <= n ; ++i)
        fin >> t[i].a >> t[i].b;
    sort(t + 1, t + n + 1);
    for(i = 1 ; i <= n ; ++i)
    {
        x = t[i].a;
        y = t[i].b;
        /// caut binar in dp cea mai din dreapta pozitie p
        /// cu dp[p].b <= x
        p = CautBin(x);
        if(dp[k].a == y) dp[k].b = max(dp[k].b, dp[p].b + y - x);
        else
        {
            k++;
            dp[k].a = y;
            dp[k].b = max(dp[k - 1].b, dp[p].b + y - x);
        }

    }
    fout << dp[k].b;

    fout.close();
    return 0;
}