Cod sursa(job #2811354)

Utilizator AleXutzZuDavid Alex Robert AleXutzZu Data 1 decembrie 2021 21:31:10
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

#define MAX_SIZE 100000

struct Sheep {
private:
    size_t wool = 0;
public:
    size_t distance = 0, max_step = 0;

    size_t getWool() const {
        return wool;
    }

    Sheep() = default;

    Sheep(std::istream &istream, size_t wolf_max_distance, size_t increment) {
        istream >> distance >> wool;
        max_step = (wolf_max_distance - distance) / increment + 1;
    }

    static bool cmp_by_step(const Sheep &_lhs, const Sheep &_rhs) {
        if (_lhs.max_step > _rhs.max_step) return true;
        if (_lhs.max_step == _rhs.max_step) return _lhs.getWool() > _rhs.getWool();
        return false;
    }
};

inline bool operator<(const Sheep &_lhs, const Sheep &_rhs) {
    return _lhs.getWool() < _rhs.getWool();
}

int main() {
    std::ifstream input("lupu.in");
    std::ofstream output("lupu.out");

    std::priority_queue<size_t> woolQueue;
    size_t n, wolf_max_distance, increment, max_step = 0;
    Sheep sheep[MAX_SIZE];
    input >> n >> wolf_max_distance >> increment;
    for (size_t i = 0; i < n; ++i) {
        sheep[i] = Sheep(input, wolf_max_distance, increment);
        if (sheep[i].max_step > max_step) max_step = sheep[i].max_step;
    }
    std::sort(sheep, sheep + n, Sheep::cmp_by_step);
    size_t index = 0;
    size_t total_wool = 0;
    /*for (size_t i = max_step; i >= 1; --i) {
        while (index < n && sheep[index].max_step == i) woolQueue.push(sheep[index++].getWool());

        if (!woolQueue.empty()) {
            total_wool += woolQueue.top();
            woolQueue.pop();
        }
    }*/
    for (int i = 0; i < max_step; ++i) total_wool += sheep[i].getWool();
    output << total_wool;
    return 0;
}