Cod sursa(job #2911504)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 30 iunie 2022 10:31:33
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

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

const int max_size = 1e6 + 1;

pair <int, int> v[max_size];
int dp[max_size];

bool cmp (pair <int, int> x, pair <int, int> y)
{
    if (x.second != y.second)
    {
        return x.second < y.second;
    }
    return x.first < y.first;
}

int main ()
{
    int n;
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> v[i].first >> v[i].second;
    }
    sort(v + 1, v + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        int x = v[i].first, y = v[i].second, r = i - 1, l = 1;
        while (l <= r)
        {
            int m = (l + r) / 2;
            if (v[m].second <= x)
            {
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }
        dp[i] = max(dp[i - 1], dp[r] + y - x);
    }
    out << dp[n];
    in.close();
    out.close();
    return 0;
}