Cod sursa(job #358741)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 24 octombrie 2009 11:45:26
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <stdio.h>
#include <vector>
#include <stdlib.h>
#define N 1<<17
using namespace std;
vector <int> v[N];
int n,TMAX;
int best[N];
void read()
{
	scanf("%d",&n);
	int i,x,y;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d",&x,&y);
		v[y].push_back(x);
		TMAX=TMAX<y ? y : TMAX;
	}
}
inline int maxim(int a,int b)
{
	return a>b ? a: b;
}
void solve()
{
	int i,j;
	for (i=1; i<=TMAX; i++)
	{
		best[i]=best[i-1];
		for (j=0; j<v[i].size(); j++)
			best[i]=maxim(best[i],best[v[i][j]]+i-v[i][j]);
	}
	printf("%d\n",best[TMAX]);
}
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	read();
	solve();
	return 0;
}