Cod sursa(job #441787)

Utilizator alin.predoiAlin Predoi alin.predoi Data 13 aprilie 2010 13:00:51
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.22 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

typedef struct a {
	int h;
	int w;
} gutuie;

bool isSmaller (gutuie a, gutuie b) {
	return a.h > b.h;
}

int main () {
	ifstream input;
	ofstream output;
	input.open ("gutui.in", ios::in);

	int N,H,U,i,nivel;
	gutuie read;
	input >>N >>H >>U;	
	
	vector<gutuie> gutui;
	vector<gutuie>::iterator it;
	vector<int> heap;
	make_heap (heap.begin(),heap.end());
	
	for (i=0;i<N;i++) {
		input >>read.h >>read.w;
		read.h = (int)((H-read.h)/U) + 1;
		gutui.push_back(read);
	}	
	input.close();

	sort(gutui.begin(), gutui.end(), isSmaller);
	nivel = gutui[0].h;
	int s=0;

	for (it = gutui.begin(); it!=gutui.end(); ++it) {	
		while (nivel > it->h) {
			if (heap.size()) {
				pop_heap(heap.begin(),heap.end());
				s += heap.back();
				heap.pop_back();
			}
			nivel--;
		}
		heap.push_back(it->w); push_heap(heap.begin(), heap.end());
		//cout <<it->h <<" " <<it->w <<endl;
	}
	while (nivel && heap.size()){
		pop_heap(heap.begin(), heap.end());
		s += heap.back();
		heap.pop_back();
		nivel--;
	}
	
	output.open ("gutui.out", ios::out);
	output << s;
	output.close();


return 0;
}