Cod sursa(job #1972070)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 21 aprilie 2017 18:52:25
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct metal
{
    int x,y;
};
metal v[100005];
int d[100005];
int cautare_binara(int st,int dr,int nr)
{
    int mid,ult=-1;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid].y<=nr)
        {
            ult=mid;
            st=mid+1;
        }
        else
            dr=mid-1;
    }
    return ult;
}
bool cmp(metal a,metal b){
    return a.y<b.y;
}
int main()
    {
        freopen("heavymetal.in","r",stdin);
        freopen("heavymetal.out","w",stdout);
        int n,i,j,max1=-1;
        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);
        for(i=1;i<=n;i++)
        {
        j=cautare_binara(1,n,v[i].x);
        d[i]=max(d[i-1],d[j]+v[i].y-v[i].x);
        if(d[i]>max1)
            max1=d[i];
        }
        printf("%d",max1);
        return 0;
    }