Cod sursa(job #2731607)

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

using namespace std;

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

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

int main(){

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

    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.front() <= i-T)                   //daca saptamana din varf <= saptamana curenta - termen de valabilitate
        {
            pret.pop_front();                    // o eliminam
            poz.pop_front();
        }
    }



    fout << suma;



    return 0;
}