Cod sursa(job #3315273)

Utilizator iustinola16Olariu Iustin iustinola16 Data 13 octombrie 2025 15:48:51
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>
#define pii pair <int, int>

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

const int NMAX = 1e5 + 5;

bool cmp(pii x, pii y)
{
    return x.second < y.second;
}

int n;
pii evenimente[NMAX];
long long dp[NMAX];
int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++)
    {
        fin >> evenimente[i].first >> evenimente[i].second;
    }

    sort(evenimente + 1, evenimente + n + 1, cmp);

    for (int i = 1; i <= n; i++)
    {
        int val = evenimente[i].first;

        int l = 1, r = n, ans = 0;
        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (evenimente[mid].second <= val)
            {
                ans = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }

        dp[i] = max(dp[i - 1], dp[ans] + evenimente[i].second - evenimente[i].first);
    }

    fout << dp[n];
    return 0;
}