Cod sursa(job #164016)

Utilizator znakeuJurba Andrei znakeu Data 23 martie 2008 13:59:04
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#include <algorithm>
#define MAXN 100005

using namespace std;

struct concert
{
	int s,e;
};

bool cmp(concert a, concert b)
{
	return a.e<b.e;
}

concert v[MAXN],a[MAXN];
int n,m;


int cb(int x)
{
	int s,e;
	s=1;
	e=m;
	while(s<e)
	{
		if (x<=v[(s+e)/2].e)
			e=(s+e)/2;
		else
			s=(s+e)/2+1;		
	}
	if(x<v[s].e)
		--s;
	return s;
}


int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	
	int i,p,profit;
	
	scanf("%d",&n);
	
	for (i=0; i<n; i++)
		scanf("%d%d",&a[i].s,&a[i].e);
	
	sort(a,a+n,cmp);
	
	v[1].e=a[0].e;
	v[1].s=a[0].e-a[0].s;
	m=1;
	for (i=1; i<n; i++)
	{
		p=cb(a[i].s);
		profit=v[p].s+a[i].e-a[i].s;
		if(a[i].e == v[m].e)
			if(profit>v[m].s)
				v[m].s=profit;
			else;
		else
		{
			if(profit<v[m].s)
				profit=v[m].s;
			v[++m].s=profit;
			v[m].e=a[i].e;			
		}
	}
	
	printf("%d\n",v[m].s);
	
	fclose(stdin);
	fclose(stdout);	
	return 0;
}