Cod sursa(job #2727181)

Utilizator XeinIonel-Alexandru Culea Xein Data 21 martie 2021 16:26:24
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <cstdlib>

#define NMax 100001

int main()
{
    std::ifstream f("branza.in");
    int N, S, T, P;
    long long Cost, Costuri[NMax];
    int Deq[NMax];
    int Front = 0, Back = 0;
    f >> N >> S >> T;
    f >> Costuri[0] >> P;

    Cost = Costuri[0] * P;
    Deq[0] = 0;
    for(int i = 1; i < N; ++i)
    {
        f >> Costuri[i] >> P;

        while(Front <= Back && Costuri[i] <= Costuri[Deq[Back]] + (i - Deq[Back]) * S)
            --Back;
        Deq[++Back] = i;

        if(i - Deq[Front] > T)
            ++Front;

        Cost += Costuri[Deq[Front]] * P + (i - Deq[Front]) * S * P;
    }
    std::ofstream g("branza.out");
    g << Cost;
    return 0;
}