Cod sursa(job #2987782)

Utilizator sorin18_2004Rata Sorin sorin18_2004 Data 2 martie 2023 20:41:56
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.58 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;

    // 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;
}