Pagini recente » Cod sursa (job #160615) | Cod sursa (job #411306) | Cod sursa (job #315014) | Cod sursa (job #2710575) | Cod sursa (job #2811574)
#include <fstream>
#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;
}
};
inline bool cmp_by_step(const Sheep &_lhs, const Sheep &_rhs) {
return _lhs.max_step > _rhs.max_step;
}
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;
}
if (!std::is_sorted(sheep, sheep + n, cmp_by_step)) std::sort(sheep, sheep + n, cmp_by_step);
size_t index = 0;
unsigned long long 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();
}
}
output << total_wool;
return 0;
}