Cod sursa(job #2987751)

Utilizator sorin18_2004Rata Sorin sorin18_2004 Data 2 martie 2023 19:44:14
Problema Lupul Urias si Rau Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#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;
    auto compare = [](pair<int, int> s1, pair<int, int> s2) {
        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()) {
        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;
}