Cod sursa(job #2987736)

Utilizator sorin18_2004Rata Sorin sorin18_2004 Data 2 martie 2023 19:02:25
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.83 kb
#include <iostream>
#include <queue>
#include <fstream>
#include <algorithm>
using namespace std;

pair<int, int> find_left_son(vector<pair<int, int>> heap, int root_index) {
    if (root_index * 2 > heap.size() - 1) return make_pair(-1, -1);

    return heap[root_index * 2 + 1];
}
pair<int, int> find_right_son(vector<pair<int, int>> heap, int root_index) {
    if (root_index * 2 + 1 > heap.size() - 1) return make_pair(-1, -1);

    return heap[root_index * 2 + 2];
}


vector<pair<int, int>> create_max_heap(vector<pair<int, int>> heap) {
    int heap_size = heap.size();
    for (int i = heap_size - 1; i > 0; i--) {
        if (heap[i].second >= heap[i / 2].second) swap(heap[i], heap[i / 2]);

    }

    return heap;
}


int main()
{
    ifstream fin("lup.in");
    ofstream fout("lup.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));
    }

    // 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
    vector<pair<int, int>> sheep_max_heap = create_max_heap(sheep);
    int total_wool = 0, steps_by_wolf = 0;



    while (!sheep_max_heap.empty()) {
        if (steps_by_wolf * sheep_step_back + sheep_max_heap[0].first <= wolf_max_step) {
            total_wool += sheep_max_heap[0].second;
            steps_by_wolf++;
        }

        sheep_max_heap.erase(sheep_max_heap.begin());
        sheep_max_heap = create_max_heap(sheep_max_heap);
    };

    fout << total_wool;

    return 0;
}