Pagini recente » Cod sursa (job #1749309) | Cod sursa (job #1880202) | Cod sursa (job #1275491) | Cod sursa (job #1475135) | Cod sursa (job #3126380)
#include <bits/stdc++.h>
#include <deque>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int v[100005];
int dequeMin[100005];
int kg[100005];
int main()
{
int n, k,s;
long long int sum = 0;
in >> n >> s >> k;
k++;
deque<int> dq;
for (int i = 1; i <= n; i++)
{
in >> v[i]>> kg[i];
}
int front= 1, back= 0;
for (int i = 1; i <= n; i++)
{
if (!dq.empty() && dq.front() == i - k)
dq.pop_front();
while (!dq.empty() && v[i] <= v[dq.back()] + s*(i - dq.back()))
dq.pop_back();
dq.push_back(i);
sum += kg[i]*(v[dq.front()] + s*(i - dq.front()));
}
out << sum;
return 0;
}