Pagini recente » Cod sursa (job #592195) | Cod sursa (job #1220969) | Cod sursa (job #334422) | Cod sursa (job #1469345) | Cod sursa (job #2730772)
#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';
}