Cod sursa(job #3154573)

Utilizator susanEmily Susan susan Data 5 octombrie 2023 10:49:17
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

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

struct event {
    long start, end;

    bool operator<(const event &other) {
        return end < other.end;
    }
};

int main() {
    vector<event> v;
    vector<int> times;

    int n;
    fin >> n;

    for (int i = 0; i < n; i++) {
        int start, finish;
        fin >> start >> finish;

        times.push_back(start);
        times.push_back(finish);
        v.push_back({start, finish});
    }

    sort(times.begin(), times.end());
    times.erase(unique(times.begin(), times.end()), times.end());

    for (event &c: v) {
        c.start = lower_bound(times.begin(), times.end(), c.start) - times.begin();
        c.end = lower_bound(times.begin(), times.end(), c.end) - times.begin();
    }

    sort(v.begin(), v.end());

    vector<int> best(times.size(), 0);

    int j = 0;
    for (int i = 0; i < times.size(); ++i) {
        if (i > 0) {
            best[i] = best[i - 1];
        }

        for (; j < n && v[j].end == i; j++) {
            best[i] = max(best[i], best[v[j].start] + times[v[j].end] - times[v[j].start]);
        }
    }

    fout << *prev(best.end());

}