Pagini recente » Cod sursa (job #75307) | Cod sursa (job #2400834) | Cod sursa (job #3244276) | Cod sursa (job #344633) | Cod sursa (job #3127099)
#include <iostream>
#include <vector>
#include <deque>
using std::cin;
using std::cout;
using std::deque;
using std::vector;
int main()
{
int n, s, t;
cin >> n >> s >> t;
deque<int> deq;
vector<int> cost(2 * n + 1);
vector<int> pret(2 * n + 1);
for (int i = 1; i <= n; i++)
{
cin >> pret[i] >> cost[i];
while (!deq.empty() && i - deq.front() > t)
{
deq.pop_front();
}
while (!deq.empty() && (pret[deq.back()] + s * (i - deq.back())) > pret[i])
{
deq.pop_back();
}
deq.push_back(i);
pret[deq.front()] += cost[i];
}
cout << pret[deq.front()];
return 0;
}