Cod sursa(job #2730781)

Utilizator icnsrNicula Ionut icnsr Data 26 martie 2021 20:52:50
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 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<std::uint64_t, std::uint64_t>> vec;
    for(unsigned 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<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();
        }

        if(!deq.empty() && i - deq.front() == T + 1)
        {
            deq.pop_front();
        }

        deq.push_back(i);

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

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