Cod sursa(job #2559146)

Utilizator MocalinnoMoca Andrei Catalin Mocalinno Data 27 februarie 2020 08:18:50
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
#define PLEC fin.close(); fout.close(); return 0;
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
unordered_map<int, int> M, nr;
vector<pair<int, int>> v;
vector<int> sorted, dp;
vector<vector<int>> before;
int n, cnt;
int main()
{
    DAU
    fin >> n;
    v = vector<pair<int, int>>(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i].first >> v[i].second;
        sorted.emplace_back(v[i].first);
        sorted.emplace_back(v[i].second);
    }
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    for (const int& x : sorted)
        M[x] = ++cnt, nr[cnt] = x;
    before = vector<vector<int>>(cnt + 1);
    for (int i = 1; i <= n; ++i)
        before[M[v[i].second]].emplace_back(M[v[i].first]);
    dp = vector<int>(cnt + 1);
    for (int i = 1; i <= cnt; ++i)
    {
        dp[i] = dp[i-1];
        for (const int& j : before[i])
            dp[i] = max(dp[i], dp[j] + nr[i] - nr[j]);
    }
    fout << dp[cnt];
    PLEC
}