Pagini recente » Cod sursa (job #1658344) | Cod sursa (job #3196351) | Cod sursa (job #2420688) | Cod sursa (job #2291473) | Cod sursa (job #3127259)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
const int MAX_ELEMENTS = 1e5 + 10;
int cheeseCost[MAX_ELEMENTS];
int main() {
ifstream inputFile("branza.in");
ofstream outputFile("branza.out");
int numWeeks, storageFee, maxStorageDuration;
inputFile >> numWeeks >> storageFee >> maxStorageDuration;
deque<int> minCostWeeks;
long long accumulatedCost = 0;
for (int week = 1; week <= numWeeks; week++) {
int productionCost, weeklyDemand;
inputFile >> productionCost >> weeklyDemand;
cheeseCost[week] = productionCost;
while (!minCostWeeks.empty() && cheeseCost[week] <= cheeseCost[minCostWeeks.back()] + storageFee * (week - minCostWeeks.back())) {
minCostWeeks.pop_back();
}
minCostWeeks.push_back(week);
while (!minCostWeeks.empty() && week - minCostWeeks.front() > maxStorageDuration) {
minCostWeeks.pop_front();
}
accumulatedCost += weeklyDemand * (cheeseCost[minCostWeeks.front()] + storageFee * (week - minCostWeeks.front()));
}
outputFile << accumulatedCost;
inputFile.close();
outputFile.close();
return 0;
}