Pagini recente » Cod sursa (job #918200) | Cod sursa (job #2936329) | Cod sursa (job #2054031) | Cod sursa (job #1101975) | Cod sursa (job #463144)
Cod sursa(job #463144)
#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;
}