Cod sursa(job #435299)

Utilizator reddeath89Dobre Valentin reddeath89 Data 7 aprilie 2010 11:32:14
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.07 kb
#include <stdio.h>
#include <stdlib.h>

#define max(a,b) (((a)>(b))?(a):(b))

typedef struct  
{
	long g;
	long h;
	long max;
	long pred;
}nivel;

int cmp(const void* a, const void* b)
{
	return ((nivel*)a)->h-((nivel*)b)->h;
}

//nivel v[10];

int main()
{
	FILE *fin=fopen("gutui.in", "rt");
	FILE *fout=fopen("gutui.out", "wt");

	long n, i=1, pi=0, h, u;
	nivel *v;

	fscanf(fin, "%ld", &n);
	++n;
	fscanf(fin, "%ld", &h);
	++h;
	fscanf(fin, "%ld", &u);

	v=(nivel*)calloc(n, sizeof(nivel));
	v[0].max=0;
	v[0].h=-u;
	v[0].g=0;

	for(i=1;i<n;++i)
	{
		fscanf(fin, "%ld%ld", &v[i].h, &v[i].g);
	}

	qsort(v,n,sizeof(nivel),cmp);
	
	--u;
	i=1; pi=v[1].pred=0;
	while(v[i].h<h && i<n)
	{
		v[i].max=max( v[i].g+v[v[i].pred].max , v[i-1].max);

		if( (v[i+1].h-v[i].h)>u) pi=v[i+1].pred=i;
		else if((v[i+1].h-v[pi].h)>u) v[i+1].pred=pi;
		else pi=v[i+1].pred=v[i].pred;

		if( v[i+1].h==v[i].h) v[i+1].g+=v[i].g;

		++i;
		++pi;
	};
	
	fprintf(fout, "%ld", v[i-1].max);
	free(v);

	fclose(fin);
	fclose(fout);
	return 0;
}