Cod sursa(job #439622)

Utilizator reddeath89Dobre Valentin reddeath89 Data 11 aprilie 2010 17:36:02
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.16 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct  
{
	long g;
	long h;
	long *nr;
}nivel;

int cmp(const void* a, const void* b)
{
	static long rez;
	rez=((nivel*)b)->g-((nivel*)a)->g;
	if(rez==0) rez=((nivel*)a)->h-((nivel*)b)->h;
	return rez;
}

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

	int n, i;
	long h, u, nivmax, nniv=0, max=0, j, st;
	nivel *v;
	long *rez, *pnt;

	fscanf(fin,"%d%ld%ld", &n, &h, &u);
	nivmax=h/u+1;

	v=(nivel*)calloc(n, sizeof(nivel));
	rez=(long*)calloc(nivmax, sizeof(long));
	pnt=(long*)calloc(nivmax+1, sizeof(long));

	for(i=0;i<n;++i)
	{
		fscanf(fin,"%ld%ld", &v[i].h, &v[i].g);
		v[i].nr=pnt+((h-v[i].h)/u);
		if(v[i].h==0) v[i].nr=pnt+(nivmax-1);
		if( v[i].h>h || v[i].g<1 ) {--i; --n;}
		
	}
	for(i=0;i<=nivmax; ++i) pnt[i]=i;

	qsort(v,n,sizeof(nivel),cmp);
	
	i=0;
	while( nniv<nivmax && i<n )
	{
		j=*(v[i].nr);
		st=*(v[i].nr+1);
		j=(j<st)?j:st;
		while(j>-1)
		{
			--(*(v[i].nr));
			if(rez[j]==0) { max+=rez[j]=v[i].g; ++nniv; break; }
			--j;
		}
		++i;
	};
	
	fprintf(fout,"%ld", max);

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