Pagini recente » Cod sursa (job #740428) | Cod sursa (job #3184294) | Cod sursa (job #2758488) | Cod sursa (job #2610009) | Cod sursa (job #3126676)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n, taxa, k, sol, dr, st = 1;
int main()
{
fin >> n >> taxa >> k;
k++;
vector<int> v(n+1);
vector<int> c(n+1);
vector<int> deq(n+1);
for (int i = 1; i <= n; i++)
fin >> v[i] >> c[i];
for (int i = 1; i <= n; i++)
{
while (dr >= st && v[i] <= v[deq[dr]] + taxa * (i - deq[dr])) dr--;
dr++;
deq[dr] = i;
if (deq[st] == i - k)
{
st++;
}
sol += v[deq[st]] + taxa * (i - deq[st]) * c[i];
}
fout << sol << endl;
return 0;
}