Cod sursa(job #2730774)

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

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

    std::uint64_t N;
    std::uint64_t S;
    std::uint64_t T;
    fin >> N >> S >> T;

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

    std::deque<std::uint64_t> deq;
    std::uint64_t suma = 0;
    for(std::uint64_t 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 std::uint64_t d_idx = deq.front();
        suma += vec[i].second * vec[d_idx].first + vec[i].second * S * (i - d_idx);
    }

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