Cod sursa(job #2600366)

Utilizator Rares5000Baciu Rares Rares5000 Data 12 aprilie 2020 14:31:41
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;

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

struct intervale
{
    int beg, endd;
}p[100005];

int n, dp[100005];

bool cmp(intervale A, intervale B)
{
    return (A.endd < B.endd || (A.endd == B.endd && A.beg < B.beg));
}

int BS(int st, int dr, int nr)
{
    int mij, poz;
    while(st <= dr)
    {
        mij = st + (dr - st) / 2;
        if(p[mij].endd <= nr)
        {
            poz = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return poz;
}

int main()
{
    int i, bss, j;
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> p[i].beg >> p[i].endd;
    sort(p + 1, p + n + 1, cmp);
    dp[1] = p[1].endd - p[1].beg;
    for(i = 2; i <= n; i++)
    {
        bss = BS(1, i - 1, p[i].beg);
        dp[i] = max(dp[i - 1], dp[bss] + p[i].endd - p[i].beg);
    }
    fout << dp[n];
    return 0;
}