Cod sursa(job #2504901)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 5 decembrie 2019 18:53:56
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

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

const int NMAX = 100000;
const int INF = 1e9;

struct sp
{
    int l, r, len;

    bool operator < (const sp other) const
    {
        if(r != other.r)
            return r < other.r;

        return l < other.l;
    }
};

int N;
sp v[4 * NMAX + 5];

vector <int> p;

unordered_map <int, int> mp;

int dp[4 * NMAX + 5];

int main()
{
    fin >> N;

    for(int i = 1; i <= N; i++)
    {
        fin >> v[i].l >> v[i].r;
        v[i].len = v[i].r - v[i].l;

        p.push_back(v[i].l);
        p.push_back(v[i].r);
    }

    int k = 0;

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

    for(auto it : p)
        if(mp[it] == 0)
            mp[it] = ++k;

    int maxT = 0;

    for(int i = 1; i <= N; i++)
    {
        v[i].l = mp[v[i].l];
        v[i].r = mp[v[i].r];

        maxT = max(maxT, v[i].r);
    }

    for(int i = 1; i <= maxT; i++)
    {
        v[++N].l = i;
        v[N].r = i;
        v[N].len = 0;
    }

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

    for(int i = 1; i <= maxT; i++)
        dp[i] = -INF;

    dp[0] = 0;

    for(int i = 1; i <= N; i++)
        dp[v[i].r] = max(dp[v[i].r], max(dp[v[i - 1].r], dp[v[i].l] + v[i].len));

    fout << dp[maxT] << '\n';

    return 0;
}