Cod sursa(job #2888843)

Utilizator Alexandru_PotangaPotanga Alexandru Alin Alexandru_Potanga Data 11 aprilie 2022 21:35:08
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
int main()
{
    int n, s, t, i;
    long long suma = 0;
    f >> n >> s >> t;

    int pret[n], cantitate[n];
    deque <int> brz;

    for(i = 0; i < n; i++)
        f >> pret[i] >> cantitate[i];

    for (i = 0; i < t; i++)
    {
        while(!brz.empty() && pret[i] <= pret[brz.back()] + s * (i - brz.back()))
            brz.pop_back();
        brz.push_back(i);

        suma = suma + cantitate[i] * (pret[brz.front()] + s * (i - brz.front()));
    }

    for (i = t; i < n; i++)
    {
        while (!brz.empty() && i - brz.front() > t)
            brz.pop_front();

        while(!brz.empty() && pret[i] <= pret[brz.back()] + s * (i - brz.back()))
            brz.pop_back();
        brz.push_back(i);

        suma = suma + cantitate[i] * (pret[brz.front()] + s * (i - brz.front()));
    }

    g << suma;

    return 0;
}