Cod sursa(job #439178)

Utilizator dilet.ibramIbram Dilet dilet.ibram Data 11 aprilie 2010 13:48:19
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.06 kb
#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
#include<fstream>
using namespace std;

bool comp1(pair<int, int> i, pair<int, int> j){
	return (i.second > j.second);
}

bool comp2(pair<int, int> i, pair<int, int> j){
	return (i.first > j.first);
}

bool pot_sa_culeg(){

}

int main(){
	vector <int> v;
	vector <pair <int, int> > cules, all_fruits;
	pair <int, int> fruit;
	int i, N, H, U, contor, greutate_totala;
	
	ifstream f_in("gutui1.in", ifstream::in);
	ofstream f_out("gutui.out", ofstream::out);
	/* citire numar de gutui din copac N
	** ialtimea maxima la care ajunge Gigel: H
	** cu cat se ridica crengile la cules: U
	*/
	f_in >> N >> H >> U;
//cout<<N<<" "<<H<<" "<<U<<"\n";
	for (i = 0; i < N; i++){
		//first = inaltilmea la care se afla
		//second = greutatea fructului
		f_in >> fruit.first >> fruit.second;
//cout<<fruit.first<<" "<<fruit.second<<"\n";
		all_fruits.push_back(fruit);
	}
	/* ordonez descrescator dupa inaltimi */
//cout<<"inainte de sort\n";
	sort(all_fruits.begin(), all_fruits.end(), comp1);
//cout<<"dupa sort\n";	

for (i = 0; i < N; i++)
	//cout<<all_fruits.at(i).first<<" "<<all_fruits.at(i).second<<"\n";
//cout<<"\n";
	cules.push_back(all_fruits.at(0));
	for (i = 1; i < N; i++){
		/* ce fructe pot baga initial (fara sa ma gandesc
		** care este cea mai buna solutie pentru greutate 
		*/
		int inaltime = all_fruits.at(i).first + U * (cules.size() - 1);
//cout<<"i = "<<i<<"; inaltime = "<<inaltime<<"\n";
		if (inaltime > H - U && inaltime <= H){
			if (all_fruits.at(i).second > cules.front().second){
				//scot minimul
				pop_heap (cules.begin(), cules.end(), comp2);
				cules.pop_back();
				//il inlocuiesc
				cules.push_back(all_fruits.at(i));
				push_heap (cules.begin(), cules.end(), comp2);
			}
		}
		else{//aici mai am nevoie de vreo conditie?!?
			cules.push_back(all_fruits.at(i));
			push_heap (cules.begin(), cules.end(), comp2);			
		}
	}
	
	greutate_totala = 0;	
	for (i = 0; i < cules.size(); i++){
		greutate_totala += cules.at(i).second;
	}
	
	f_out << greutate_totala;
	f_out.close();
	f_in.close();
	return 0;
}