Cod sursa(job #440183)

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

typedef struct  
{
	int g;
	int h;
	int nr;
}nivel;

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

int nniv=0, _max=0;

int addrez(int *v, int nod, int st, int dr, int b, int g)
{
	int mij, rst, rdr;
	if(v[nod]!=0) return v[nod];
	if(dr==st) {_max+=g; ++nniv; return v[nod]=g;}

	mij=(st+dr)/2;
	
	if(b>mij && v[nod*2+2]==0)
	{
		rst=nniv;
		rdr=addrez(v, nod*2+2, mij+1, dr, b, g);
		if (nniv==rst) rst=addrez(v, nod*2+1, st, mij, b, g);
		else rst=v[nod*2+1];
	}
	else
	{
		rdr=v[nod*2+2];
		rst=addrez(v, nod*2+1, st, mij, b, g);
	}

	return v[nod]=((rst<rdr)?rst:rdr);
}

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

	int n, i;
	int h, u, nivmax;
	nivel *v;
	int *act;

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

	v=(nivel*)calloc(n, sizeof(nivel));
	act=(int*)calloc(i, sizeof(int));

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

	qsort(v,n,sizeof(nivel),cmp);

	i=0;
	while( nniv<nivmax && i<n )
	{
		addrez(act, 0, 0, nivmax-1, v[i].nr, v[i].g);
		++i;
	};

	fprintf(fout,"%d", _max);

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