Cod sursa(job #522213)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 14 ianuarie 2011 16:03:58
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct formatie 
{
	int x,y;
};
formatie f[100010];
int t[100010];
bool cmp(formatie a,formatie b)
{
	return a.y<b.y;
}
int main()
{
	freopen("havymetal.in","r",stdin);
	freopen("havymetal.out","w",stdout);
	int last,max,i,n;
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%ld%ld",&f[i].x,&f[i].y);
	sort(f+1,f+n+1,cmp);
	max=f[n].y;
	last=1;
	for (i=1;i<=max;i++)
	{
		t[i]=t[i-1];
		while (f[last].y==i)
		{
			if (t[i]<t[f[max].x]+i-t[f[last].x])
				t[i]=t[f[max].x]+i-t[f[last].x];
			last++;
		}
	}
	printf("%ld",t[i-1]);
}