Cod sursa(job #2731593)

Utilizator cosminradu1760Cosmin-Andrei Radu cosminradu1760 Data 27 martie 2021 23:01:05
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");

deque<int> pret, poz; // puteam folosi la fel de usor un deque de tupluri

int main(){

    int N, T, S, C, P, suma;

    suma = 0;

    fin >> N >> S >> T;

    for(int i = 0; i < N; i++)
    {
        fin>>C>>P;

        while(!pret.empty() && pret.back() + S * (i - poz.back()) >= C) // cat timp cozile nu sunt goale si costul de productie al saptamanii anterioare +
        {                                                               //pretul de depozitare al saptamanilor anterioare e mai mare ca si costul de productie curent
            pret.pop_back();                                            //eliminam din deques pretul si pozitia saptamanii anterioare
            poz.pop_back();
        }
        pret.push_back(C);                                              //adaugam pretul si pozitia saptamanii curente la dreapta
        poz.push_back(i);

        suma += P * (pret.front() + S * (i - poz.front()));
                                                        // crestem suma

        if(poz.back() <= i-T)                   //daca saptamana din varf <= saptamana curenta - termen de valabilitate
        {
            pret.pop_back();                    // o eliminam
            poz.pop_back();
        }
    }



    fout << suma;



    return 0;
}