Pagini recente » Cod sursa (job #2317344) | Cod sursa (job #498655) | Cod sursa (job #2634867) | Cod sursa (job #1452441) | Cod sursa (job #3126353)
#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;
int sum = 0;
in >> n >> s >> k;
k=k+1;
for (int i = 1; i <= n; i++)
{
in >> v[i]>> kg[i];
}
int front= 1, back= 0;
for (int i = 1; i <= n; i++)
{
while(front <= back && v[i] - s*(back-front +1) < v[dequeMin[front]])
front++;
back++;
dequeMin[back]=i;
if (dequeMin[front] == i-k) front++;
sum += kg[i] * v[dequeMin[front]];
for (size_t j = front +1; j <= back; j++)
{
sum += kg[dequeMin[back]]*s;
}
}
out << sum;
return 0;
}