Cod sursa(job #2987991)

Utilizator tomaionutIDorando tomaionut Data 3 martie 2023 11:38:24
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
#define Android ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;

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

int n, dp[100005];
struct vrajeala
{
    int x, y;
    bool operator < (const vrajeala A) const
    {
        if (y == A.y)
            return x < A.x;
        return y < A.y;
    }
}a[100005];

void Test_Case()
{
    int i, j, st, dr, mij, sol;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i].x >> a[i].y;
    sort(a + 1, a + n + 1);

    for (i = 1; i <= n; i++)
    {
        st = sol = 1;
        dr = i - 1;
        while (st <= dr)
        {
            mij = (st + dr) / 2;
            if (a[mij].y <= a[i].x)
            {
                st = mij + 1;
                sol = mij;
            }
            else dr = mij - 1;
        }
        dp[i] = max(dp[i - 1], dp[sol] + a[i].y - a[i].x);
    }
    fout << dp[n];
}

int32_t main()
{
    Android
    int t;
    t = 1;
    while (t--)
        Test_Case();

    return 0;
}