Cod sursa(job #3127259)

Utilizator dandragosDan Dragos dandragos Data 7 mai 2023 13:58:52
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#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;
}