Cod sursa(job #2737835)

Utilizator Ionut15Marcu Ionut Ionut15 Data 5 aprilie 2021 11:00:48
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

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

struct P {
    int x;
    int y;
};
P v[100001];
int sol[100001];
int n;
int main()
{
    in >> n;
    for (int i = 1; i <= n; i++) {
        int a, b;
        in >> a >> b;
        v[i] = { a,b };
    }
    sort(v + 1, v + n + 1, [](P a, P b) {
        if (a.x > b.x) return false;
        else if (a.x < b.x) return true;
        else return a.y < b.y;
        });
    int j = 1;
    for (int i = 1; i <= v[n].y; i++) {
        sol[i] = sol[i - 1];
        while (v[j].y == i) {
            sol[i] = max(sol[i], sol[v[j].x] + v[j].y - v[j].x);
            j++;
        }
    }
    out << sol[v[n].y];
    return 0;
}