Cod sursa(job #2833727)

Utilizator Stefan_GhinescuGhinescu Stefan-George Stefan_Ghinescu Data 15 ianuarie 2022 15:47:59
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 100000;

struct Inter
{
    int b, e;
};

Inter v[NMAX + 5];
int dp[NMAX + 5], w[NMAX + 5];

bool cmp(const Inter& a, const Inter& b)
{
    if (a.e == b.e)
    {
        return a.b < b.b;
    }
    return a.e < b.e;
}

int bs(int n, int x)
{
    int r = 0, pas = 1 << 16;
    while (pas)
    {
        if (r + pas <= n && w[r + pas] <= x)
        {
            r += pas;
        }
        pas >>= 1;
    }
    return r;
}

int main()
{
    int n;
    fin >> n;
    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i].b >> v[i].e;
    }
    sort(v + 1, v + n + 1, cmp);
    int i, j;
    for (i = 1, j = 1; j <= n; ++i)
    {
        w[i] = v[j].e;
        dp[i] = dp[i - 1];
        while (j <= n && w[i] == v[j].e)
        {
            int b = bs(i, v[j].b);
            dp[i] = max(dp[i], dp[b] + v[j].e - v[j].b);
            ++j;
        }
    }
    fout << dp[i - 1];
    return 0;
}