Cod sursa(job #1431072)

Utilizator horatiu11Ilie Ovidiu Horatiu horatiu11 Data 8 mai 2015 23:33:25
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
//horatiu11
# include <cstdio>
# include <algorithm>
# define nmax 100001
using namespace std;
int n,sol[nmax];
struct interval{int a,b;}v[nmax];
inline bool cmp(interval x, interval y)
{
    return (x.b<y.b);
}
int main()
{
    int i,l,r,m,poz;
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d%d",&v[i].a,&v[i].b);
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;++i)
    {
        l=1;r=i-1;poz=0;
        while(l<=r)
        {
            m=(l+r)/2;
            if(v[m].b<=v[i].a)l=m+1,poz=m;
            else r=m-1;
        }
        sol[i]=max(sol[i-1],sol[poz]+v[i].b-v[i].a);
    }
    printf("%d\n",sol[n]);
    return 0;
}