Cod sursa(job #2885462)

Utilizator RaduIonescuRadu Ionescu RaduIonescu Data 6 aprilie 2022 02:04:27
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,cantitate,costprod[1000002];

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

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

        if (!deq.empty() && deq.back() == 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 += 1LL*(cantitate * (costprod[deq.front()] + (zi - deq.front()) * pretdepoz)); /// adaugam costul zilei curente
    }

    out<<total;

    return 0;
}