Cod sursa(job #2048312)

Utilizator leraValeria lera Data 25 octombrie 2017 22:06:17
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda hlo2017_cj_av_l4 Marime 1.05 kb
#include <iostream>
#include <fstream>
#define Nmax 100005
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,m,j;
long long dp[Nmax],val[Nmax],val2[Nmax],maxim,ls,ld,mij;
pair<int,int>p[Nmax];
bool cmp(pair<int,int>a,pair<int,int>b)
{
    return(a.second<b.second);
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    fin>>p[i].first>>p[i].second;
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)if(p[i].second!=p[i-1].second)
        val[++m]=p[i].second;
    for(int i=1;i<=n;i++)
        {
            ls=0;ld=m;
            while(ls<ld)
            {
                mij=(ls+ld)/2+1;
                if(val[mij]<=p[i].first)ls=mij;
                else ld=mij-1;
            }
            val2[i]=ls;
        }
    j=1;
    for(int i=1;i<=m;i++)
    {
        dp[i]=dp[i-1];
        while(val[i]==p[j].second && j<=n)
        {
            dp[i]=max(dp[i],dp[val2[j]]+p[j].second-p[j].first);
            j++;
        }
    }
    fout<<dp[m];
    return 0;
}