Pagini recente » Cod sursa (job #1491213) | Cod sursa (job #1012436) | Cod sursa (job #2541693) | Cod sursa (job #86605) | Cod sursa (job #2269275)
#include <fstream>
#include <queue>
#include <algorithm>
struct Sheep
{
int distance;
int fluffiness;
};
int main()
{
std::ifstream fin("lupu.in");
int nSheeps, maxCatchDistance, stepDistance;
std::vector<Sheep> sheeps;
fin >> nSheeps >> maxCatchDistance >> stepDistance;
sheeps.insert(sheeps.begin(), static_cast<unsigned long>(nSheeps), {});
for(int i = 0; i < nSheeps; i++)
fin >> sheeps[i].distance >> sheeps[i].fluffiness;
std::sort(sheeps.begin(), sheeps.end(), [](const Sheep &lhs, const Sheep &rhs){
return lhs.distance < rhs.distance;
});
std::priority_queue<int> availableSheeps;
unsigned long long fluffiness = 0;
auto it = sheeps.begin();
int currentStep = maxCatchDistance / stepDistance;
while(currentStep >= 0)
{
while(it != sheeps.end() && it->distance + currentStep * stepDistance <= maxCatchDistance)
{
availableSheeps.push(it->fluffiness);
it++;
}
if(!availableSheeps.empty())
{
fluffiness += availableSheeps.top();
availableSheeps.pop();
}
currentStep --;
}
std::ofstream fout("lupu.out");
fout << fluffiness;
return 0;
}