Cod sursa(job #340300)

Utilizator DraStiKDragos Oprica DraStiK Data 14 august 2009 09:46:34
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda w3 Marime 0.89 kb
#include <algorithm>
#define DIM 1000005
#define LogN 18
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].b,&v[i].a);
}
int cmp (concert a,concert b)
{
    return a.a<b.a || (a.a==b.a && a.b<b.b);
}
int cbin (int val)
{
	int nr=0,put=LogN;
	while (put--) 
        if (nr+(1<<(put))<=n) 
            if (v[nr+(1<<(put))].a<=val)
                nr+=(1<<(put));
	return nr;
}
int max (int a,int b)
{
	if (a>b) 
        return a;
	return b;
}
void solve ()
{
    int i,x;    
	for (i=1; i<=n; ++i)
	{
		b[i]=b[i-1];
		x=cbin (v[i].b);
		b[i]=max(b[i],b[x]+v[i].a-v[i].b);
	}
	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;
}