Cod sursa(job #1033196)

Utilizator vladrochianVlad Rochian vladrochian Data 16 noiembrie 2013 16:21:07
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <fstream>
#include <algorithm>
using namespace std;
struct band
{
	int s,e;
}b[100001];
int n,i,pd[100001];
bool cmp(band b1,band b2)
{
	if(b1.e==b2.e)
		return b1.s<b2.s;
	return b1.e<b2.e;
}
int bs(int s,int e,int lim)
{
	if(s==e)
		return s-1;
	int m=(s+e)/2;
	if(b[m].e>lim)
		return bs(s,m,lim);
	return bs(m+1,e,lim);
}
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int main()
{
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>b[i].s>>b[i].e;
	sort(b+1,b+n+1,cmp);
	for(i=1;i<=n;i++)
		pd[i]=max(pd[i-1],b[i].e-b[i].s+pd[bs(0,i,b[i].s)]);
	fout<<pd[n]<<"\n";
	return 0;
}