Cod sursa(job #2638586)

Utilizator loraclorac lorac lorac Data 28 iulie 2020 22:10:58
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int lim=1e5+4;
const int inf=2e9+7;
pair<int,int> v[lim];
int dp[lim];
bool mycmp(pair<int,int> p1,pair<int,int> p2)
{
    if(p1.second==p2.second)
        return p1.first>p2.first;
    return p1.second<p2.second;
}
int main()
{
    int n;
    in>>n;
    for(int i=1;i<=n;++i)
        in>>v[i].first>>v[i].second;
    sort(v+1,v+n+1,mycmp);
    int l,r,med;
    for(int i=1;i<=n;++i)
    {
        dp[i]=dp[i-1];
        if(v[i].first<v[1].second)
            dp[i]=max(dp[i],v[i].second-v[i].first);
        else
        {
            l=1,r=i-1;
            while(l<r)
            {
                if(r==l+1)
                    med=r;
                else med=(l+r)/2;
                if(v[med].second<=v[i].first)
                    l=med;
                else r=med-1;
            }
            dp[i]=max(dp[i],dp[l]+v[i].second-v[i].first);
        }
    }
    out<<dp[n]<<'\n';
    return 0;
}