Cod sursa(job #520377)

Utilizator bora_marianBora marian bora_marian Data 8 ianuarie 2011 12:04:45
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
 #include<fstream>
#include<algorithm>
using namespace std;
int n,best[100020], p[100020];
struct intervale{
	int x,y;};
intervale v[100020];
int comp(int i, int j)
{
	if(v[i].y<v[j].y)
	   return 1;
	return 0;
}
int maxim(int a,int b)
{
	if(a>b)
	  return a;
	else
	  return b;
}     
int rez;
void cautare(int st,int dr,int val);
int main()
{
	ifstream fin("heavymetal.in");
	ofstream fout("heavymetal.out");
	fin>>n;
	int i;
	for(i=1;i<=n;i++)
	    fin>>v[i].x>>v[i].y, p[i]=i;
	sort(p+1,p+n+1,comp);
	best[1]=v[p[1]].y-v[p[1]].x;
	for(i=2;i<=n;i++)
	{
		rez=0;
		cautare(1,i-1,v[p[i]].x);
		int sol=rez;
		best[i]=maxim(best[i-1],best[sol]+v[p[i]].y-v[p[i]].x);
	}
	fout<<best[n];
	return 0;
}
void cautare(int st,int dr,int val)
{
   if(st==dr)
   {
	   if(v[p[st]].y<=val && st>rez)
	      rez=st;
	   return ;
   }
   else
   {
	   int mijloc=(st+dr)/2;
	   if(v[p[mijloc]].y<=val)
	   {
		   if(mijloc>rez)
		      rez=mijloc;
		   cautare(mijloc+1,dr,val);
		}
		else
		   cautare(st,mijloc,val);
	}
}