Pagini recente » Cod sursa (job #1373342) | Cod sursa (job #3261326) | Cod sursa (job #232193) | Cod sursa (job #2554466) | Cod sursa (job #2987782)
#include <iostream>
#include <queue>
#include <fstream>
#include <algorithm>
using namespace std;
int main()
{
ifstream fin("lupu.in");
ofstream fout("lupu.out");
vector<pair<int, int>> sheep;
int sheep_count, wolf_max_step, sheep_step_back;
fin >> sheep_count >> wolf_max_step >> sheep_step_back;
for (int i = 0; i < sheep_count; i++) {
int wool_quantity, distance;
fin >> distance >> wool_quantity;
sheep.push_back(make_pair(distance, wool_quantity));
}
int total_wool = 0, steps_by_wolf = 0;
// order the sheep descending by the amount of wool
auto compare = [](pair<int, int> s1, pair<int, int> s2) {
if (s1.second == s2.second) return s1.first > s2.first;
return s1.second < s2.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compare)> sheep_max_heap{ compare, sheep };
// to maximize the wool quantity we will use a greedy aproach:
// take the first sheep available(that can be reached by the wolf) from a max-heap based on wool quantity
while (!sheep_max_heap.empty()) {
cout << sheep_max_heap.top().first << " " << sheep_max_heap.top().second << endl;
// check if the wolf can reach the current max-wool sheep, and increase the sheep distance
if (steps_by_wolf * sheep_step_back + sheep_max_heap.top().first <= wolf_max_step) {
total_wool += sheep_max_heap.top().second;
steps_by_wolf++;
}
sheep_max_heap.pop();
};
fout << total_wool;
return 0;
}