Cod sursa(job #2982788)

Utilizator rastervcrastervc rastervc Data 20 februarie 2023 21:09:57
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

struct Spectacle {
    long long start, end;
};

constexpr size_t MAX_N = 1e5 + 1;
long long N, dp[MAX_N];
Spectacle v[MAX_N];

bool compare(Spectacle a, Spectacle b) {
    if (a.end != b.end) return a.end < b.end;
    return a.start < b.start;
}

int main() {
    fin >> N;
    for (long long i = 1; i <= N; i++)
        fin >> v[i].start >> v[i].end;

    sort(v + 1, v + N + 1, compare);

    long long ans = 0;
    for (long long i = 1; i <= N; i++) {
        long long l = 1, r = N;
        while (l <= r) {
            long long mid = (l + r) / 2;
            if (v[mid].end > v[i].start) r = mid - 1;
            else l = mid + 1;
        }

        dp[i] = max(dp[i - 1], dp[r] + v[i].end - v[i].start);
        ans = max(ans, dp[i]);
    }

    fout << ans;
    return 0;
}