Cod sursa(job #1206842)

Utilizator ccygnusMaygnus Pop ccygnus Data 11 iulie 2014 12:49:45
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct metal
{
	int x,y;
};
metal v[100005];
int d[100005];
int cmp(metal a,metal b)
{
	return a.y<b.y;
}
int bs(int st,int dr,int val)
{
	int med,last=-1;
	while(st<=dr)
	  {
	  /*med=(st+dr)/2
	  med=st+(dr-st)/2;*/
	  med=(st+dr)>>1;
	  if (v[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 n,i,last;
	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);
	d[1]=v[1].y-v[1].x;
	for(i=2;i<=n;i++)
		{
		d[i]=d[i-1];
		last=bs(1,i-1,v[i].x);
		if (last==-1)
			{
			if (d[i]<v[i].y-v[i].x)
				d[i]=v[i].y-v[i].x;
			}
		else
			if (d[i]<d[last]+v[i].y-v[i].x)
				d[i]=d[last]+v[i].y-v[i].x;
		}
	printf("%d\n",d[n]);
return 0;
}