Pagini recente » Cod sursa (job #1270215) | Cod sursa (job #397474) | Cod sursa (job #427802) | Cod sursa (job #142762) | Cod sursa (job #2811275)
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX_SIZE 100000
struct Sheep {
private:
size_t wool = 0;
public:
size_t distance = 0;
size_t getWool() const {
return wool;
}
Sheep() = default;
explicit Sheep(std::istream &istream) {
istream >> distance >> wool;
}
};
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, std::vector<size_t>> woolQueue;
size_t n, wolf_max_distance, increment;
std::vector<Sheep> sheep;
std::vector<size_t> step;
input >> n >> wolf_max_distance >> increment;
sheep.reserve(n);
for (int i = 0; i < n; ++i) sheep.emplace_back(input);
step.reserve(n);
for (int i = 0; i < n; ++i) step.push_back((wolf_max_distance - sheep[i].distance) / increment + 1);
size_t max_step = *std::max_element(step.cbegin(), step.cend()), total_wool = 0;
for (size_t i = max_step; i >= 1; --i) {
for (int j = 0; j < n; ++j) if (step[j] == i) woolQueue.push(sheep[j].getWool());
if (!woolQueue.empty()) {
total_wool += woolQueue.top();
woolQueue.pop();
}
}
output << total_wool;
return 0;
}