Cod sursa(job #2888084)

Utilizator iulia.talpalariuIulia-Georgiana Talpalariu iulia.talpalariu Data 10 aprilie 2022 17:47:48
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>


int main() {
    std::ifstream fileIn("branza.in");
    std::ofstream fileOut("branza.out");
    int n, pret_stocare, k, i;
    long long int pret, kg, minimum = 0 ;
    std:: deque <int> dQ;
    std::vector <long long int> pret_branza;
    fileIn >> n >> pret_stocare >> k;

    for(i = 0; i < n; i++) {
        fileIn >> pret >> kg;
        pret_branza.push_back(pret);
        while (!dQ.empty() && pret <= pret_branza[dQ.back()] + pret_stocare*(i-dQ.back())) {
            dQ.pop_back();
        }

        dQ.push_back(i);

        if(dQ.back() < i-k) {
            dQ.pop_front();
        }

        minimum += (pret_branza[dQ.front()]+ pret_stocare * (i- dQ.front())) * kg;

    }
    fileOut << minimum;



    return 0;
}