Cod sursa(job #140725)

Utilizator swift90Ionut Bogdanescu swift90 Data 22 februarie 2008 10:29:28
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 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;
	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;
}