Cod sursa(job #2004558)

Utilizator victoreVictor Popa victore Data 26 iulie 2017 10:20:03
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<cstdio>
#include<algorithm>

using namespace std;

const int nmax=1e5+5;

struct al
{
    int x,y;
}v[nmax];
int dp[nmax];

inline bool cmp(al a,al b)
{
    return a.y<b.y;
}

inline int bsearch(int dr,int x)
{
    int i,step;
    if(dr==0)
        return 0;
    for(step=1;step<dr;step<<=1);
    for(i=1;step;step>>=1)
        if(i+step<=dr && v[i+step].y<=x)
            i+=step;
    return i;
}

int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d%d",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    int lng,poz;
    for(i=1;i<=n;++i)
    {
        lng=v[i].y-v[i].x;
        poz=bsearch(i-1,v[i].x);
        dp[i]=dp[poz]+lng;
    }
    int maxim=0;
    for(i=1;i<=n;++i)
        if(maxim<dp[i])
            maxim=dp[i];
    printf("%d",maxim);
}