Cod sursa(job #463390)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 15 iunie 2010 16:53:21
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.59 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

//structura pentru gutuie
typedef struct a {
	int h;
	int w;
} gutuie;

//functie de comparatie necesara sortarii
bool isGreater (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;				//valoare aux pentru citire
	input >>N >>H >>U;	
	
	vector<gutuie> gutui;			//valorile gutuilor
	vector<gutuie>::iterator it;		//iterator pe gutui
	vector<int> heap;			//heapul ce tine valorile gutuilor
	make_heap (heap.begin(),heap.end());	//initializare heap
	
	for (i=0;i<N;i++) {			//citire
		input >>read.h >>read.w;
		read.h = (int)((H-read.h)/U) + 1;
		gutui.push_back(read);		//nivel
	}	
	input.close();

	sort(gutui.begin(), gutui.end(), isGreater);	//sortez descrescator dupa nivel
	nivel = gutui[0].h;
	int s=0;

	for (it = gutui.begin(); it!=gutui.end(); ++it) {		// pentru fiecare gutuie
		while (nivel > it->h) {					// daca nivelul_curent > nivelul gutuii
			if (heap.size()) {				
				pop_heap(heap.begin(),heap.end());	// inseamna ca pot lua gutui de pe nivelurile anterioare
				s += heap.back();
				heap.pop_back();
			}
			nivel--;
		}
		heap.push_back(it->w); push_heap(heap.begin(), heap.end()); // pun (fiecare) gutuie in heap
	}
	while (nivel && heap.size()){			// daca mai pot lua gutui (si mai am de unde)
		pop_heap(heap.begin(), heap.end());
		s += heap.back();			// extrag gutuile ramase
		heap.pop_back();
		nivel--;
	}
	
	output.open ("gutui.out", ios::out);
	output << s;
	output.close();


return 0;
}