Cod sursa(job #2885454)

Utilizator RaduIonescuRadu Ionescu RaduIonescu Data 6 aprilie 2022 01:42:29
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<bits/stdc++.h>

using namespace std;

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

deque <long long> deq;

long long n,pretdepoz,expirare,total=0,cantitate,costprod[100002];

int main()
{
    in>>n>>pretdepoz>>expirare;

    for(int zi = 1; zi<=n ;zi++)
    {
        in >> costprod[zi] >> cantitate;

        if (!deq.empty() && deq.front() == zi - expirare)  deq.pop_front();  ///eliminam branza expirata

        while (!deq.empty() && costprod[deq.back()] + (zi - deq.back()) * pretdepoz > costprod[zi])  deq.pop_back();    ///verificam daca e mai rentabil sa lasam la pastrat sau sa producem branza

        deq.push_back(zi);  ///ziua curenta

        total += cantitate * (costprod[deq.front()] + (zi - deq.front()) * pretdepoz); /// adaugam costul zilei curente
    }

    out<<total;

    return 0;
}