Cod sursa(job #610594)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 28 august 2011 11:22:03
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n,best[100010];
struct Spectacol{int x,y;};
Spectacol a[100010];

void Citire()
{
	int i;
	ifstream fin("heavymetal.in");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>a[i].x>>a[i].y;
	fin.close();
}

int CautareBinara(int x,int capat)
{
	int st,dr,m;
	st=1; dr=capat;
	while(st<=dr)
	{
		m=(st+dr)/2;
		if(a[m].y<=x && a[m+1].y>x)
			return m;
		if(a[m].y<=x)
			st=m+1;
		else dr=m-1;
	}
	return 0;
}

inline bool Ordonare(Spectacol A,Spectacol B)
{
	return A.y<B.y;
}

void Rezolvare()
{
	int i,poz;
	sort(a+1,a+n+1,Ordonare);
	best[1]=a[1].y-a[1].x;
	for(i=2;i<=n;i++)
	{
		poz=CautareBinara(a[i].x,i-1);
		best[i]=max(best[i-1],best[poz]+a[i].y-a[i].x);
	}
}

void Afisare()
{
	ofstream fout("heavymetal.out");
	fout<<best[n]<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Rezolvare();
	Afisare();
	return 0;
}