Cod sursa(job #779945)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 19 august 2012 16:15:01
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<fstream>
#include<algorithm>
#define dim 100007
using namespace std;

ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
struct cub {
	int x,y;
}
v[dim];
int  cmp (cub a, cub b){
	return a.y<b.y;
}
inline int max (int a,int b){
	if(a<b)
		return b;
	return a;
}
int Max,b[dim],cnt[1006],i,j,n,T;
int main () {
	
	f>>n;
	
	for(i=1;i<=n;++i){
		f>>v[i].x>>v[i].y;
		if(v[i].y	>T)
			T=v[i].y;
		cnt[v[i].y]++;
	}
	
	sort(v+1,v+1+n,cmp);
	
	for(i=1; i<=T; ++i ) {
		
		b[i]=b[i-1];
		
		if(!cnt[i])
			continue;
		
		for(j=1 ;j<=n; ++j ) {
			
			if(v[j].y==i){
				b[i]=max(b[i],b[v[j].x]+v[j].y-v[j].x);
				if(cnt[v[j].y]==1)
					break;
			}
			
		}
		if(b[i]>Max)
			Max=b[i];
	}
	g<<Max<<"\n";
	return 0;
}