Cod sursa(job #1692209)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 20 aprilie 2016 14:34:52
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct INTERV
{
	int x,y;
};
INTERV v[100005];
int d[100005];
bool cmp(INTERV a,INTERV b)
{
	return a.y<b.y;
}
int bs(int st,int dr,int val)
{
	int med;
	while(st<=dr)
	{
		med=(st+dr)/2;
		if(v[med].y<=val) st=med+1;
		else dr=med-1;
	}
	return st-1;
}
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,x,y,i,j,ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
    	scanf("%d%d",&x,&y);
    	v[i].x=x;
    	v[i].y=y;
    	d[i]=-1;
    }
    d[0]=0;
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
    {
    	j=bs(1,i-1,v[i].x);
    	d[i]=max(d[i-1],d[j]+v[i].y-v[i].x);
    	ans=max(ans,d[i]);
    }
    printf("%d\n",ans);
    return 0;
}