Cod sursa(job #2579099)

Utilizator FrostfireMagirescu Tudor Frostfire Data 11 martie 2020 22:31:59
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#define NMAX 100000

using namespace std;

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

int n, dp[2*NMAX+10];
struct date
{   int x, y, c;
}v[NMAX+10];
vector <int> a;
vector <pair <int, int> > val[2*NMAX+10];
unordered_map <int, int> umap;

int main()
{
    f >> n;
    for(int i=1; i<=n; i++)
        {   f >> v[i].x >> v[i].y;
            v[i].c = v[i].y - v[i].x;
            a.push_back(v[i].x);
            a.push_back(v[i].y);
        }
    sort(a.begin(), a.end());
    int nr = 1;
    umap[a[0]] = 1;
    for(int i=1; i<a.size(); i++)
        {   if(a[i] != a[i-1]) nr++;
            umap[a[i]] = nr;
        }
    for(int i=1; i<=n; i++)
        {   v[i].x = umap[v[i].x];
            v[i].y = umap[v[i].y];
            val[v[i].y].push_back(make_pair(v[i].c, v[i].x));
        }
    for(int i=1; i<=nr; i++)
        {   dp[i] = dp[i-1];
            for(int j=0; j<val[i].size(); j++) dp[i] = max(dp[i], val[i][j].first + dp[val[i][j].second]);
        }
    g << dp[nr] << '\n';
    return 0;
}