Cod sursa(job #437817)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 10 aprilie 2010 02:49:24
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.28 kb
# include <iostream>
# include <fstream>
# include <cstdlib>

# 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()
{
	std::ifstream f("gutui.in",std::ios::in);
	f >> n;
	f >> h;
	f >> u;
	long int i;
	for (i=1;i<=n;i++){
		f >> gutui[i].h;
		f >> gutui[i].w;
		gutui[i].tic = (h-gutui[i].h)/u + 1;
		//nu ne intereseaza gutuile care sunt peste inaltimea h
		if (gutui[i].h > h){
			i--;
			n--;
		}
	}
	f.close();
	qsort(gutui+1,n,sizeof(GUTUIE),comparaGutui);
}

void scrie(long int sol)
{
	std::ofstream g("gutui.out",std::ios::out | std::ios::trunc);
	g << sol << "\n";
	g.close();
}

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