Pagini recente » Cod sursa (job #103986) | Cod sursa (job #409377) | Cod sursa (job #1194300) | Cod sursa (job #2583442) | Cod sursa (job #3126355)
#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;
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;
}