Cod sursa(job #434699)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 6 aprilie 2010 14:02:22
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.23 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>
#include<sys/types.h>
using namespace std;
#define height first
#define weight second
#define poh pop_heap
#define pob pop_back
#define pub push_back
#define puh 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() {
	uint32_t n,h,u,i,j,k;
	uint64_t sum = 0;
	ifstream f("gutui.in",ios::in);
	ofstream g("gutui.out",ios::out);
	vector<pair<uint32_t,uint32_t> > x, aux;
	f>>n>>h>>u;
	for(i=0;i<n;i++) {
		f>>j>>k;
		x.push_back(make_pair(j,k));
	}
	sort(x.begin(),x.end(),sortHeight);	
	aux.push_back(x[0]);
	make_heap(aux.begin(),aux.end(),sortWeight);
	for(i=1;i<n;i++) {
		if(aux.size()==(1+(h-x[i].height)/u) && aux.front().weight<x[i].weight) {
			poh(aux.begin(),aux.end(),sortWeight);
			aux.pob();
			aux.pub(make_pair(x[i].height,x[i].weight));
			puh(aux.begin(),aux.end(),sortWeight);
		}			
		else if(aux.size()!=(1+(h-x[i].height)/u))
		{			
			aux.pub(make_pair(x[i].height,x[i].weight));
			puh(aux.begin(),aux.end(),sortWeight);
		}
	}	
	for (i=0; i<aux.size(); i++)
		sum+=aux[i].weight;
	g<<sum;
return 0;
}