Cod sursa(job #2730772)

Utilizator icnsrNicula Ionut icnsr Data 26 martie 2021 20:36:41
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <cstddef>
#include <vector>
#include <fstream>
#include <deque>

int main()
{
    std::ifstream fin("branza.in");
    std::ofstream fout("branza.out");

    unsigned N;
    unsigned S;
    unsigned T;
    fin >> N >> S >> T;

    std::vector<std::pair<unsigned, unsigned>> vec;
    for(std::size_t i = 0; i < N; ++i)
    {
        unsigned v1;
        unsigned v2;
        fin >> v1 >> v2;
        vec.push_back(std::make_pair(v1, v2));
    }

    std::deque<unsigned> deq;
    std::uint64_t suma = 0;
    for(unsigned i = 0; i < N; ++i)
    {
        while(!deq.empty() && vec[i].first <= vec[deq.back()].first + S * (i - deq.back()))
        {
            deq.pop_back();
        }
        deq.push_back(i);

        if(i - deq.front() == T)
        {
            deq.pop_front();
        }

        const unsigned d_idx = deq.front();
        suma += vec[i].second * (vec[d_idx].first + S * (i - d_idx));
    }

    fout << suma << '\n';
}