Cod sursa(job #2729090)

Utilizator vladstefanVlad Oros vladstefan Data 24 martie 2021 10:05:58
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb

// problema heavymetal

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>

#define NMax 100000

using namespace std;

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

int n;

struct secv {
    int a, b;
};

vector<int> pozitii, paux, DP;
vector<secv> secvente;

void input() {
    int a, b;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> a >> b;
        secvente.push_back({a, b});
        paux.push_back(a);
        paux.push_back(b);
    }
}

int findpos(int pos) {
    return lower_bound(pozitii.begin(), pozitii.end(), pos) - pozitii.begin();
}

void init() {
    auto f = [](secv x, secv y) {
        if (x.b < y.b) return 1;
        if (x.b > y.b) return 0;
        if (x.a <= y.a) return 1;
        return 0;
    };
    sort(secvente.begin(), secvente.end(), f);
    
    //
    
    sort(paux.begin(), paux.end());
    for (auto p = paux.begin(); p < paux.end(); ++p) {
        pozitii.push_back(*p);
        while (*p == *(p + 1)) ++p;
    }
    
    //
    
    auto ps = secvente.begin();
    auto ppoz = pozitii.begin();
    int a, b;
    DP.push_back(0);
    for (++ppoz; ppoz < pozitii.end(); ++ppoz) {
        for (; (*ps).b < *ppoz; ++ps);
        b = ppoz - pozitii.begin();
        DP.push_back(DP[b - 1]);
        for (; (*ps).b == *ppoz; ++ps) {
            a = findpos((*ps).a); // unde se afla "a"
            DP[b] = max(DP[b], DP[a] + (*ps).b - (*ps).a);
        }
    }
}

void solve() {
    fout << *(DP.end() - 1);
}

int main() {
    input();
    init();
    solve();
}