Cod sursa(job #2505613)

Utilizator trifangrobertRobert Trifan trifangrobert Data 7 decembrie 2019 09:18:27
Problema Heavy metal Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5 + 5;
int n;
pair <int, int> a[NMAX];
vector <int> v[2 * NMAX];
map <int, int> nrm;
int invnrm[2 * NMAX];
int dp[2 * NMAX];

int main()
{
    ifstream fin("heavymetal.in");
    ofstream fout("heavymetal.out");
    fin >> n;
    int x, y;
    for (int i = 1;i <= n;++i)
    {
        fin >> a[i].first >> a[i].second;
        nrm[a[i].first] = 1;
        nrm[a[i].second] = 1;
    }
    int nrmval = 0;
    for (auto &i : nrm)
    {
        i.second = ++nrmval;
        invnrm[nrmval] = i.first;
    }
    for (int i = 1;i <= n;++i)
    {
        a[i].first = nrm[a[i].first];
        a[i].second = nrm[a[i].second];
        v[a[i].second].push_back(a[i].first);
    }
    n = nrmval;
    for (int i = 1;i <= n;++i)
    {
        dp[i] = dp[i - 1];
        for (auto &j : v[i])
            dp[i] = max(dp[i], dp[j] + (invnrm[i] - invnrm[j]));
    }
    fout << dp[n] << "\n";
    fin.close();
    fout.close();
    return 0;
}