Cod sursa(job #1804654)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 12 noiembrie 2016 20:57:13
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<bits/stdc++.h>
#define maxN 100005
using namespace std;
pair<int,int> v[maxN];
int n,dp[maxN],x,st,dr,mid,sol;
bool cmp(pair <int,int> a,pair<int,int> b)
{
    if(a.second<b.second) return 1;
    return 0;
}
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].first,&v[i].second);
    }
    sort(v+1,v+n+1,cmp);
    dp[1]=v[1].second-v[1].first;
    for(int i=2;i<=n;i++)
    {
        dp[i]=dp[i-1];
        x=v[i].first;
        st=1;
        dr=i-1;
        sol=0;
        while(st<=dr)
        {
            mid=(st+dr)>>1;
            if(v[mid].second<=x)
            {
                sol=mid;
                st=mid+1;
            }
                else dr=mid-1;
        }
        dp[i]=max(dp[i],dp[sol]+v[i].second-v[i].first);
    }
    printf("%d\n",dp[n]);
    return 0;
}