Cod sursa(job #516498)

Utilizator ChallengeMurtaza Alexandru Challenge Data 24 decembrie 2010 14:04:53
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>

using namespace std;

const char InFile[]="heavymetal.in";
const char OutFile[]="heavymetal.out";
const int MaxN=100111;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_inter
{
	s_inter(int x2=0,int y2=0):x(x2),y(y2){}
	int x,y;
};

struct cmp
{
	inline bool operator() (const s_inter &a, const s_inter &b)
	{
		return a.y<b.y;
	}
};

s_inter v[MaxN];
int N,best[MaxN];

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>v[i].x>>v[i].y;
	}
	fin.close();

	sort(v+1,v+1+N,cmp());

	for(register int i=1;i<=N;++i)
	{
		int p=1;
		int u=i-1;
		int sol=-1;
		while(p<=u)
		{
			int m=p+((u-p)>>1);
			if(v[m].y>v[i].x)
			{
				u=m-1;
			}
			else
			{
				sol=m;
				p=m+1;
			}
		}
		best[i]=max(best[sol-1],best[sol]+v[i].y-v[i].x);
	}

	fout<<best[N];
	fout.close();
	return 0;
}