Cod sursa(job #142300)

Utilizator swift90Ionut Bogdanescu swift90 Data 24 februarie 2008 13:24:35
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define maxn 100010
pair <int, int> nr[maxn];
int best[maxn],timp[maxn],n,x,maxim;
inline int max(int a,int b){
	return a>b?a:b;
}	
int caut(int i){
	int p=0,u=x-1,mij;
	while(p!=u){
		mij=(p+u)/2;
		if(nr[i].second<=timp[mij])
			u=mij;
		else
			p=mij+1;
	}
	return p;
}
void dinamic(int i){
	int poz,interval;
	if(timp[x]<nr[i].first){
		++x;
		best[x]=best[x-1];
	}
	poz=caut(i);
	interval=nr[i].first-nr[i].second;
	timp[x]=nr[i].first;
	while(timp[poz]>nr[i].second)
		--poz;
	best[x]=max(best[x],best[poz]+interval);
	if(best[x]>maxim)
		maxim=best[x];
}
int main(){
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int i;
	scanf("%d",&n);
	for(i=0;i<n;++i)
		scanf("%d%d",&nr[i].second,&nr[i].first);
	sort(nr,nr+n);
	for(i=0;i<n;++i)
		dinamic(i);
	
	printf("%d\n",maxim);
	fclose(stdin);
	fclose(stdout);
	return 0;
}