Cod sursa(job #439178)
#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;
}