Cod sursa(job #2047669)

Utilizator AlexTheDagonBogdan Tudor AlexTheDagon Data 25 octombrie 2017 09:26:50
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define NM 200005
#define pb push_back
#define x first
#define y second
#define mp make_pair
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int n,nor[NM],nrmact,dp[NM];
vector<int> srt;
vector<pair<int,int> > v;
pair<int,int> ult;
map<int,int> mm;
int main()
{
    int a,b;
    in>>n;
    for(int i=1;i<=n;++i)
    {
      in>>a>>b;
      srt.pb(a);
      srt.pb(b);
      v.pb(mp(b,a));
    }
    sort(srt.begin(),srt.end());
    sort(v.begin(),v.end());
    for(auto i:srt)
      if(mm.find(i)==mm.end())
      {
        ++nrmact;
        mm[i]=nrmact;
        nor[nrmact]=i;
      }
    for(int i=0;i<v.size();++i)
    {
      swap(v[i].x,v[i].y);
      v[i].x=mm[v[i].x];
      v[i].y=mm[v[i].y];
    }
    for(int i=1,ind=0;i<=nrmact;++i)
    {
      while(ind<v.size() && v[ind].y==i)
      {
        dp[v[ind].y]=max(dp[v[ind].y],dp[v[ind].x]+(nor[i]-nor[v[ind].x]));
        ++ind;
      }
      dp[i]=max(dp[i],dp[i-1]);
    }
    out<<dp[nrmact];
    return 0;
}