Cod sursa(job #535643)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 17 februarie 2011 16:01:51
Problema Heavy metal Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 100001
using namespace std;
FILE *f=fopen("heavymetal.in","r");
FILE *g=fopen("heavymetal.out","w");
struct timp{
	int a;
	int b;
} v[NMAX];
int ind[NMAX],sol[NMAX],N;
int cmp(const int &x,const int &y){
	return v[x].b < v[y].b;	
}
int cautare_binara(int val,int z){
	int p=0,sl=0,u=z;
	while(p<=u){
		int m=(p+u)/2;
		if( v[ind[m]].b == val)
			{sl=m;break;}
		else if(v[ind[m]].b < val)
			    p=m+1,sl=m;
		else u=m-1;
	}
	int pz=sl;
for(int st=sl;st>=1 && v[st].b==val;st--)
	if(sol[st] > sol[sl])
		sl=st;
for(int dr=pz;dr<=z && v[dr].b==val;dr++)
	if(sol[dr] > sol[sl])
		pz=dr;
return max(sl,pz);
}
int main(){
	fscanf(f,"%d",&N);
	for(int i=1;i<=N;++i){
		fscanf(f,"%d%d",&v[i].a,&v[i].b);
		ind[i]=i;}
	sort(ind+1,ind+N+1,cmp);
	sol[1]=v[ind[1]].b-v[ind[1]].a;
	for(int i=2;i<=N;++i)
		sol[i]=max(sol[i-1],v[ind[i]].b-v[ind[i]].a+sol[cautare_binara(v[ind[i]].a,i-1)]);
	fprintf(g,"%d",sol[N]);
return 0;
}