Cod sursa(job #2729707)

Utilizator stefanvoicaVoica Stefan stefanvoica Data 25 martie 2021 09:59:24
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <bits/stdc++.h>
#define dim 100002
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout("heavymetal.out");
long long    nr[2*dim],dp[2*dim];
unordered_map<long long   ,long long   > asoc;


struct el
{
    long long    a,b;
}v[dim];


inline bool cmp (const el &a1,const el &a2)
{
    if (a1.a==a2.a)
        return a1.b<a2.b;
    return a1.a<a2.a;
}

int main()
{
    long long  n,i,ct=1,j=1;
    fin>>n;
    for (i=1;i<=n;i++)
    {
        fin>>v[i].a>>v[i].b;
        nr[2*i]=v[i].b;
        nr[2*i-1]=v[i].a;
    }
    sort(nr+1,nr+2*n+1);
    sort(v+1,v+n+1,cmp);
    for (i=1;i<=2*n;i++)
        if (nr[i]!=nr[i-1])
            asoc[nr[i]]=ct++;
    for (i=1;i<=n;i++)
    {
        while (j<=asoc[v[i].b])
        {
            dp[j]=max(dp[j],dp[j-1]);
            ++j;
        }
        dp[asoc[v[i].b]]=max(dp[asoc[v[i].b]],dp[asoc[v[i].a]]+v[i].b-v[i].a);
    }
    fout<<dp[ct-1]<<'\n';
}