Cod sursa(job #435357)

Utilizator reddeath89Dobre Valentin reddeath89 Data 7 aprilie 2010 12:39:04
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.16 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)
{
	static int rez;
	rez=((nivel*)a)->h-((nivel*)b)->h;
	if(rez==0) rez=((nivel*)a)->g-((nivel*)b)->g;
	return rez;
}

//nivel v[12];

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+1, 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);
	v[n].h=v[n-1].h+2;
	
	--u;
	i=1; 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);

		pi=v[i].pred;
		while (v[pi].h<v[i+1].h)
		{
			if((v[i+1].h-v[pi].h)>u) v[i+1].pred=pi;
			else break;
			++pi;
		}

		//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;
}