Cod sursa(job #2760597)

Utilizator MadalinaKopaczMadalina Kopacz MadalinaKopacz Data 28 iunie 2021 02:08:40
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");

//problema de deque
//avem in deque costurile in ord cresc

int N, T, S, P;
int C[100005];
deque<int> D;

int Rezultat()
{
    int cmin = 0;
    for (int i = 0; i < N; i++)
    {
        fin >> C[i] >> P;
        //minimizam costurile (costul curent e mai mic decat costul de depozitare+costul din sapt prec
        while (!D.empty() && C[i] <= C[D.back()] + S * (i - D.back())) D.pop_back();   
        //adaugam costul la coada
        D.push_back(i);
        //am iesit din secventa de T
        if (!D.empty() && D.front() == i - T)  D.pop_front(); 
        //adaugam la cheltuielile totale
        cmin += P * (C[D.front()] + S * (i - D.front()));   
    }
    return cmin;
}
int main() 
{
    fin >> N >> S >> T; 
    T++;
    fout << Rezultat();
}