Cod sursa(job #2886519)

Utilizator AndreiAncutaAndrei Ancuta AndreiAncuta Data 7 aprilie 2022 20:51:53
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <deque>
#include <fstream>
#include <vector>

int main() {
    std::ifstream ifs("branza.in");
    std::ofstream ofs("branza.out");

    unsigned weeks, storage_cost, shelf_life;
    ifs >> weeks >> storage_cost >> shelf_life;

    unsigned long long total_cost = 0;
    std::vector<unsigned> cost_at_week(weeks);
    std::deque<unsigned> min_cost_week;
    for (std::size_t week = 1; week <= weeks; week++) {
        unsigned cost, amount;
        ifs >> cost >> amount;
        cost_at_week[week] = cost;

        while (!min_cost_week.empty() &&
               min_cost_week.front() + shelf_life < week) {
            // Cheese produced in the current cheapest week is too old to be
            // sold from now on, so eliminate the current cheapest week.
            min_cost_week.pop_front();
        }

        // Eliminate from the deque all earlier weeks that are more expensive
        // per kg than the current week.
        while (!min_cost_week.empty()) {
            auto earlier_week = min_cost_week.back();
            auto cost_to_produce_earlier = cost_at_week[earlier_week];
            auto storage_duration = week - earlier_week;
            auto cost_to_store_earlier = storage_duration * storage_cost;
            if (cost < cost_to_produce_earlier + cost_to_store_earlier) {
                // The current week will always be cheaper per kg than the
                // earlier one, so eliminate the earlier one.
                min_cost_week.pop_back();
            } else {
                break;
            }
        }
        min_cost_week.push_back(week);

        auto min_week = min_cost_week.front();
        auto cost_to_produce_in_min_week = cost_at_week[min_week] * amount;
        auto cost_to_store_since_min_week =
            (week - min_week) * storage_cost * amount;
        total_cost +=
            cost_to_produce_in_min_week + cost_to_store_since_min_week;
    }

    ofs << total_cost << '\n';

    ifs.close();
    ofs.close();

    return 0;
}