Cod sursa(job #2988001)

Utilizator PalcPalcu Stefan Palc Data 3 martie 2023 11:47:29
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;

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

int n;
long long dp[100005];
pair<long long, long long> t[100005];

bool cmp(pair<long long, long long> A, pair<long long, long long> B)
{
    return A.second < B.second;
}

long long CB(long long x)
{
    long long st, dr, mij, p;
    st = 1; dr = n; p = 0;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (t[mij].second <= x)
        {
            st = mij + 1;
            p = mij;
        }
        else dr = mij - 1;
    }
    return p;
}

int main()
{
    long long p;
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> t[i].first >> t[i].second;
    sort(t + 1, t + n + 1, cmp);
    dp[1] = t[1].second - t[1].first;
    for (int i = 1; i <= n; i++)
    {
        p = CB(t[i].first);
        dp[i] = max(dp[i - 1], dp[p] + t[i].second - t[i].first);
    }
    fout << dp[n] << "\n";
    return 0;
}