Cod sursa(job #434607)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 6 aprilie 2010 11:16:55
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.15 kb
# include <stdio.h>
# include <stdlib.h>

# define MAXN 100000

typedef struct GUTUIE{
	long int h,w,tic;
} GUTUIE;

int comparaGutui(const void *aa, const void *bb)
{
	GUTUIE* a = (GUTUIE*) aa;
	GUTUIE* b = (GUTUIE*) bb;
	if (a->tic < b->tic) return -1;
	if (a->tic > b->tic) return 1;
	if (a->w   > b->w  ) return 1;
	if (a->w   < b->w  ) return -1;
	return 0;
}

GUTUIE gutui[MAXN+1];
long int n,u,h;

//acesta este un MIN-HEAP (contine in varf mereu INDEXUL la cea mai usoara gutuie)
class HEAP{

private:
	long int v[MAXN+1];
	long int len;

	void surface(long int i){
		long int aux;
		while (i/2 && gutui[v[i]].w < gutui[v[i/2]].w){
			aux = v[i]; v[i] = v[i/2]; v[i/2] = aux;
			i/=2;
		}
	}

	void submerge(long int i){
		long int aux,min;
		do{
			min = i;
			if (2*i  <= len && gutui[v[2*i  ]].w < gutui[v[min]].w) 	min = 2*i;
			if (2*i+1<= len && gutui[v[2*i+1]].w < gutui[v[min]].w) 	min = 2*i+1;
			if (i==min) break;
			aux = v[i]; v[i] = v[min]; v[min] = aux;
			i = min;
		} while (1);
	}

public:
	HEAP(){
		len = 0;
	}
	
	void insert(long int i){
		v[++len] = i;
		surface(len);
	}

	long int topWeight(){
		return gutui[v[1]].w;
	}

	long int extract(){
		long int sol = v[1];
		v[1] = v[len];
		len --;
		submerge(1);
		return sol;
	}

	long int totalSum(){
		long int i, sol = 0;
		for (i=1;i<=len;i++)
			sol += gutui[v[i]].w;
		return sol;
	}
};



void citire()
{
	FILE *f=fopen("gutui.in","r");
	fscanf(f,"%ld%ld%ld",&n,&h,&u);
	long int i;
	for (i=1;i<=n;i++){
		fscanf(f,"%ld%ld",&gutui[i].h,&gutui[i].w);
		gutui[i].tic = (h-gutui[i].h)/u + 1;
	}
	fclose(f);
	qsort(gutui+1,n,sizeof(GUTUIE),comparaGutui);
}

void scrie(long int sol)
{
	FILE *g=fopen("gutui.out","w");
	fprintf(g,"%ld\n",sol);
	fclose(g);
}

void calculeaza()
{
	HEAP h;
	long int i,lasttic = 0;
	//iteram prin toate gutuile. Retinem mereu la ce "tic" suntem :D
	for (i=1;i<=n;i++){
		//daca poti sa o culegi linistit
		if (gutui[i].tic > lasttic){
			h.insert(i);
			lasttic++;
		} else if (h.topWeight() < gutui[i].w){ //ai optiunea sa o inlocuiesti cu una pe care deja ai cules'o
			h.extract();
			h.insert(i);
		}
	}
	scrie(h.totalSum());
}

int main()
{
	citire();
	calculeaza();
	return 0;
}