Cod sursa(job #435371)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 7 aprilie 2010 12:54:40
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.7 kb
// Dobrota Valentin-Eugen, 324CA, PA, Tema1, Prob2 - Gutui, 2009-2010
#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>
#include<sys/types.h>
using namespace std;
#define height first
#define weight second
#define pb push_back
#define ph push_heap
bool sortWeight(pair<uint32_t,uint32_t>i,pair<uint32_t,uint32_t>j) {
	return(i.weight>j.weight);
}
bool sortHeight(pair<uint32_t,uint32_t>i,pair<uint32_t,uint32_t>j) {
	return(i.height>j.height);
}
int main() {
	// Declarari
	uint32_t n,h,u,i,j,k;
	uint64_t sum = 0;
	ifstream f("gutui.in",ios::in);
	ofstream g("gutui.out",ios::out);
	// Datele de intrare
	vector<pair<uint32_t,uint32_t> > x;
	// Heapul auxiliar
	vector<pair<uint32_t,uint32_t> > aux;
	// Citiri
	f>>n>>h>>u;
	for(i=0;i<n;i++) {
		f>>j>>k;
		x.push_back(make_pair(j,k));
	}
	// Ordonare descrescator dupa inaltimi
	sort(x.begin(),x.end(),sortHeight);	
	// In heap tinem minte initial cea mai inalta gutuie
	aux.push_back(x[0]);
	// Pentru fiecare gutuie, de la cea mai inalta la cea mai joasa
	for(i=1;i<n;i++) {
		// Daca heapul e plin, dar putem imbunatati suma:
		if(aux.size()==(1+(h-x[i].height)/u) && aux.front().weight<x[i].weight) {
			// Facem schimb intre cea mai usoara gutuie din heap si gutuia curenta
			pop_heap(aux.begin(),aux.end(),sortWeight);
			aux.pop_back();
			aux.pb(make_pair(x[i].height,x[i].weight));
			ph(aux.begin(),aux.end(),sortWeight);
		}	
		// Daca heapul nu e plin inseram gutuia curenta		
		else if(aux.size()!=(1+(h-x[i].height)/u))
		{			
			aux.pb(make_pair(x[i].height,x[i].weight));
			ph(aux.begin(),aux.end(),sortWeight);
		}
	}
	// Raspunsul este suma greutatilor gutuilor din heap	
	for (i=0; i<aux.size(); i++)
		sum+=aux[i].weight;
	g<<sum;
return 0;
}