Pagini recente » Cod sursa (job #845932) | Cod sursa (job #2362104) | Cod sursa (job #1326928) | Cod sursa (job #415517) | Cod sursa (job #3126397)
#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++;
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 += 1LL*kg[i] * (v[dequeMin[front]] +(i - dequeMin[front]) * s) ;
}
out << sum;
return 0;
}