Cod sursa(job #2887337)

Utilizator mihairazvan03Dana Mihai mihairazvan03 Data 9 aprilie 2022 13:32:14
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <stack>
#include <fstream>

using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");

long long n, s, t, i, pret, cerere, suma, minActual;
deque<pair<long, pair<long, long>>> saptamaniDeq;    //<pos, <pret, cerere>>
int main()
{

    in >> n >> s >> t;

    for(i = 1; i <= n; i++)
    {
        in >> pret >> cerere;

        while(saptamaniDeq.empty() == false && saptamaniDeq.back().first + t < i)  //inseamna ca a expirat si eliminam din deq sapt care au termenul depasit
            saptamaniDeq.pop_back();

        //acum ne raman in deq numai sapt care pot produce pt sapt in care ne aflam acum

        while(saptamaniDeq.empty() == false && pret < saptamaniDeq.front().second.first + (i - saptamaniDeq.front().first) * s)  //dam pop in fata pana cand nu mai avem un pret mai bun
            saptamaniDeq.pop_front();


        if(saptamaniDeq.empty() == false && saptamaniDeq.front().second.first + (i - saptamaniDeq.front().first) * s < pret)
            minActual = minActual = saptamaniDeq.front().second.first + (i - saptamaniDeq.front().first) * s;
        else
            minActual = pret;

        suma += minActual * cerere;

        saptamaniDeq.push_front(make_pair(i, make_pair(pret, cerere)));
    }

    out<<suma;

    return 0;
}