Cod sursa(job #2894526)

Utilizator AlexMariMarinescu Alexandru AlexMari Data 27 aprilie 2022 22:22:16
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

long long n, dp[100005];

struct elem
{
    long long val1, val2;
}v[100005];

inline bool cmp(const elem a, const elem b)
{
    return a.val2 < b.val2;
}

int main()
{
    fin >> n;
    for (long long i = 1; i <= n; i++) {
        fin >> v[i].val1 >> v[i].val2;
    }

    sort(v + 1, v + n + 1, cmp);
    for (long long i = 1; i <= n; i++) {
        long long st = 1, dr = i - 1, poz = 0;
        while (st <= dr) {
            long long mijl = (st + dr) / 2;
            if (v[i].val1 >= v[mijl].val2) {
                st = mijl + 1;
                poz = mijl;
            } else {
                dr = mijl - 1;
            }
        }
        dp[i] = max(dp[i - 1], dp[poz] + v[i].val2 - v[i].val1);
    }

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