Cod sursa(job #2055206)

Utilizator vancea.catalincatalin vancea.catalin Data 2 noiembrie 2017 22:46:20
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#define DX 200050
using namespace std;
fstream fin("heavymetal.in",ios::in),fout("heavymetal.out",ios::out);
map<int,int> mp,pm;
int n,nr,dp[DX],maxi;
struct cls
{
    int a,b;
    bool operator < (const cls& cl) const
    {
        if(b<=cl.b)
            return 1;
        else
            return 0;
    }
};
vector<int> norm;
vector<cls> v;
void normalizare()
{
    int i,j;
    sort(norm.begin(),norm.end());
    for(i=0;i<norm.size();i++)
    {
        nr++;
        mp[norm[i]]=nr;
        pm[nr]=norm[i];
        for(j=i;((j<norm.size()) && (norm[i]==norm[j]));j++);
        i=j-1;
    }
}
void solv()
{
    int i,j=0,a,b,c;
    for(i=2;i<=nr;i++)
    {
        dp[i]=dp[i-1];
        while(j<v.size() && v[j].b<=pm[i])
        {
            a=mp[v[j].a]; b=mp[v[j].b]; c=v[j].b-v[j].a;

            dp[i]=max(dp[i],dp[a]+c);
            j++;
        }
        maxi=max(maxi,dp[i]);
    }
}
int main()
{
    int i,j,a,b;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        v.push_back({a,b});
        norm.push_back(a); norm.push_back(b);
    }
    //normalizare();
    sort(v.begin(),v.end());

    //solv();
    fout<<maxi;
}