Cod sursa(job #2269265)

Utilizator alexge50alexX AleX alexge50 Data 25 octombrie 2018 20:16:11
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#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;
}