Cod sursa(job #727816)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 28 martie 2012 12:06:25
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb

#include <fstream>
#include <algorithm>
#include <vector>

struct oaie
{
    unsigned int distanta;
    unsigned int lana;
} oi [100000];

bool compara (struct oaie a, struct oaie b)
{
    return a.lana < b.lana;
}

int main (void)
{
    std::ifstream input("lupu.in");
    unsigned int aux,distanta_max,distanta;
    input >> aux >> distanta_max >> distanta;
    struct oaie *ptr(oi),*limit(oi + aux);
    unsigned int timp((static_cast<unsigned int>(1) << 31) - 1);
    do
    {
        input >> ptr->distanta >> ptr->lana;
        if (ptr->distanta < timp)
            timp = ptr->distanta;
        ++ptr;
    }
    while (ptr < limit);
    input.close();
    timp = distanta_max - timp;
    timp /= distanta;
    std::sort(oi,limit,compara);
    --ptr;
    aux = 0;
    ++timp;
    unsigned int ocupate(0);
    long long result(0);
    std::vector<bool> momente(timp + 1,false);
    std::vector<bool>::iterator m;
    unsigned int aux2;
    while (ocupate < timp)
    {
        while (ptr->distanta + aux > distanta_max && ptr >= oi)
            --ptr;
        if (ptr < oi)
            break;
        aux2 = (ptr->distanta + aux) / distanta;
        m = momente.begin() + aux2;
        while (*m)
            --m;
        *m = true;
        result += ptr->lana;
        aux += distanta;
        ++ocupate;
        --ptr;
    }
    std::ofstream output("lupu.out");
    output << result << '\n';
    output.close();
    return 0;
}