Pagini recente » Cod sursa (job #946216) | Cod sursa (job #3283475) | Cod sursa (job #2860663) | Cod sursa (job #2204167) | Cod sursa (job #3126399)
#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;
}