Pagini recente » Cod sursa (job #2409241) | Cod sursa (job #2558234) | Cod sursa (job #1536309) | Cod sursa (job #1985256) | Cod sursa (job #3126410)
#include <bits/stdc++.h>
#include <deque>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
long long int v[100005];
long long int dequeMin[100005];
long long 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++)
{
if (dequeMin[front] == i-k) front++;
while(front <= back && v[i] - s*(i-dequeMin[back]) < v[dequeMin[back]])
back--;
back++;
dequeMin[back]=i;
sum += kg[i] * (v[dequeMin[front]] +(i - dequeMin[front]) * s) ;
}
out << sum;
return 0;
}