Pagini recente » Cod sursa (job #400372) | Cod sursa (job #915433) | Cod sursa (job #3197146) | Cod sursa (job #2835398) | Cod sursa (job #2886519)
#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;
}