Pagini recente » Cod sursa (job #3165484) | Cod sursa (job #545169) | Cod sursa (job #2972013) | Cod sursa (job #2265363) | Cod sursa (job #2730774)
#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';
}