Cod sursa(job #3127265)

Utilizator dandragosDan Dragos dandragos Data 7 mai 2023 14:02:04
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

const int MAXN = 1e5 + 10;
int cost[MAXN];

int main() {
    ifstream inFile("branza.in");
    ofstream outFile("branza.out");

    int n;
    int storageCost, maxWeeks;
    inFile >> n >> storageCost >> maxWeeks;

    long long totalCost = 0;
    for (int i = 1; i <= n; i++) {
        int curCost, curDemand;
        inFile >> curCost >> curDemand;
        cost[i] = curCost;

        while (!m.empty() && cost[i] <= cost[m.back()] + storageCost * (i - m.back())) {
            m.pop_back();
        }
        m.push_back(i);

        while (!m.empty() && i - m.front() > maxWeeks) {
            m.pop_front();
        }
        totalCost += curDemand * (cost[m.front()] + storageCost * (i - m.front()));
    }

    outFile << totalCost;

    inFile.close();
    outFile.close();

    return 0;
}