Cod sursa(job #927132)

Utilizator smaraldaSmaranda Dinu smaralda Data 25 martie 2013 16:41:42
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

struct TYPE { int x, y; };
TYPE c[100010];
int res[100010];
bool cmp(TYPE a, TYPE b)
{
    return a.y<b.y;
}

int bs (int val, int dr)
{
    int st=1,med,last;
    last=0;
    while(st<=dr)
        {
            med=(st+dr)>>1;
            if(c[med].y<=val)
                {
                    last=med;
                    st=med+1;
                }
            else
                dr=med-1;
        }
    return last;
}
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int poz,t1,t2,n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        {
            scanf("%d%d",&t1,&t2);
            c[i].x=t1; c[i].y=t2;
        }
    sort(c+1,c+1+n,cmp);
    for(i=1;i<=n;i++)
        {
            poz=bs(c[i].x,i-1);
            res[i]=max(res[i-1],res[poz]+c[i].y-c[i].x);
        }
    printf("%d\n",res[n]);
    return 0;
}