Cod sursa(job #301293)

Utilizator DraStiKDragos Oprica DraStiK Data 8 aprilie 2009 08:56:41
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <algorithm>
#define DIM 1000005
using namespace std;
struct concert {int a,b;} v[DIM];
int b[DIM];
int n;
void read ()
{
    int i;
    scanf ("%d",&n);
	for (i=1; i<=n; ++i)
		scanf ("%d%d",&v[i].a,&v[i].b);
}
int cmp (concert a,concert b)
{
    return a.b<b.b || (a.b==b.b && a.a<b.a);
}
int cbin (int val)
{
	int st,dr,mij,nr;
	for (st=1, dr=n; st<=dr; )
	{
		mij=(st+dr)/2;
		if (v[mij].a==val)
			nr=mij;
		if (v[mij].a>=val)
			dr=mij-1;
		else
			st=mij+1;
	}
	return nr-1;
}
int max (int a,int b)
{
	if (a>b) 
        return a;
	return b;
}
void solve ()
{
    int i;    
	for (i=1; i<=n; ++i)
	{
		b[i]=b[i-1];
		b[i]=max(b[i],b[cbin (v[i].a)]+v[i].b-v[i].a);
	}
	printf("%d\n", b[n]);
}
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	read ();
	sort(v+1,v+n+1,cmp);
    solve ();
	return 0;
}