Cod sursa(job #664765)

Utilizator danalex97Dan H Alexandru danalex97 Data 20 ianuarie 2012 19:15:07
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
using namespace std;

int a[100001],b[100001];
int n,i,j;
long long best[100001],maxim[100001];

int pozitionare(int st,int dr)
{
	int xst,xdr;
	xst=0;
	xdr=-1;
	while (st<dr)
		if (b[st]<b[dr])
		{
			st+=xst;
			dr+=xdr;
		}
	else
	{
        swap(b[st],b[dr]);
        swap(a[st],a[dr]);
        xst=1-xst;
        xdr=-1-xdr;
        st+=xst;
		dr+=xdr;
	}
	return st;
}

void cautbin(int st,int dr)
{
	int mij=(st+dr)/2;
	if (st!=dr)
	{
		if (b[mij]>a[i])
			cautbin(st,mij-1);
		else
			if (b[mij+1]<=a[i])
				cautbin(mij+1,dr);
			else
				cautbin(mij,mij);
	}
	else
	j=st;
}

void quick(int st,int dr)
{
	int p=pozitionare(st,dr);
	if (st<p-1)
		quick(st,p-1);
	if (p+1<dr)
		quick(p+1,dr);
}

int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;++i)
		scanf("%d%d",&a[i],&b[i]);
	quick(1,n);
	best[1]=b[1]-a[1];
	maxim[1]=best[1];
	for (i=2;i<=n;++i)
	{
		cautbin(1,i-1);
		best[i]=b[i]-a[i];
		maxim[i]=maxim[i-1];
		if (b[j]<=a[i])
			best[i]+=maxim[j];
		if (best[i]>maxim[i])
			maxim[i]=best[i];
	}
	printf("%lld\n",maxim[n]);
	return 0;
}