Cod sursa(job #439580)

Utilizator dilet.ibramIbram Dilet dilet.ibram Data 11 aprilie 2010 17:13:39
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.18 kb
#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
#include<fstream>

using namespace std;

/* fructele sunt perechi (de tipul pair)
	first = inaltimea la care se afla fructul
	second = greutatea fructului 		*/

/* pentru minheap dupa greutate (second) 	*/
bool comp2(pair<int, int> i, pair<int, int> j){
	return (i.second > j.second);
}

/* pentru ordonare descrescatoare dupa inatimi 	*/
bool comp1(pair<int, int> i, pair<int, int> j){
	return (i.first > j.first);
}

int main(){
	vector <pair <int, int> > all_fruits;/* toate fructele initiale */
	vector <pair <int, int> > cules;/* heapul final cu ce am cules 	*/
	pair <int, int> fruit;
	int i, N, H, U;
	unsigned long long int  greutate_totala;
	
	ifstream f_in("gutui.in", ifstream::in);
	ofstream f_out("gutui.out", ofstream::out);
	/* citiri: */
	f_in >> N >> H >> U;
	for (i = 0; i < N; i++){
		f_in >> fruit.first >> fruit.second;
		all_fruits.push_back(fruit);
	}
	
	/* ordonare descrescator dupa inaltimi 	*/
	sort(all_fruits.begin(), all_fruits.end(), comp1);
	
	/* introducere prim element in heap: 	*/
	cules.push_back(all_fruits.at(0));
	/* alegerea celor mai bune greutati din restul de fructe: 	*/
	for (i = 1; i < N; i++){
		/* inaltimea la care se afla fructul curent 		*/
		int inaltime = all_fruits.at(i).first + U * (cules.size());
		/* daca gutuia curenta poate imbunatati starea gutuilor deja
		** culese 						*/
		if (inaltime > H  && inaltime <= H + U){
			if (all_fruits.at(i).second > cules.front().second){
			/* daca greutatea descoperita e mai mare decat minimul
			** curent din heap, il scot si il inlocuiesc =>
			** in acest moment am cea mai buna combinatie din 
			** gutuile care au apucat a fi tratate 		*/
				pop_heap (cules.begin(), cules.end(), comp2);
				cules.pop_back();
				cules.push_back(all_fruits.at(i));
				push_heap (cules.begin(), cules.end(), comp2);
			}
		}
		else{
			cules.push_back(all_fruits.at(i));
			push_heap (cules.begin(), cules.end(), comp2);			
		}
	}
	
	/* calcul greutate totala obtinuta 	*/
	greutate_totala = 0;
	int dim = cules.size();	
	for (i = 0; i < dim; i++)
		greutate_totala += cules.at(i).second;
		
	f_out << greutate_totala;
	f_out.close();
	f_in.close();
	return 0;
}