Cod sursa(job #440039)

Utilizator reddeath89Dobre Valentin reddeath89 Data 11 aprilie 2010 21:35:12
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 1.49 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;
}

long 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=(v[nod*2+1]==0)?addrez(v, nod*2+1, st, mij, b, g):v[nod*2+1];
		else rst=v[nod*2+1];
	}
	else
	{
		rdr=v[nod*2+2];
		rst=(v[nod*2+1]==0)?addrez(v, nod*2+1, st, mij, b, g):v[nod*2+1];
	}

	return v[nod]=((rst<rdr)?rst:rdr);
}
//long act[30];

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

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

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

	v=(nivel*)calloc(n, sizeof(nivel));
	act=(long*)calloc(nivmax*2-1, sizeof(long));

	for(i=0;i<n;++i)
	{
		fscanf(fin,"%ld%ld", &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,"%ld", _max);

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