Pagini recente » Cod sursa (job #1158345) | Cod sursa (job #2044573) | Cod sursa (job #929650) | Cod sursa (job #1278967) | Cod sursa (job #2887283)
#include <fstream>
int c[5000010], p[5000010];
int deq[5000010];
int main()
{
std::ifstream fin("branza.in");
std::ofstream fout("branza.out");
int n, s, k;
fin >> n >> s >> k;
for (int i = 0; i < n; ++i) fin >> c[i] >> p[i];
int front = 0, back = 0;
long long sum = 0;
for (int i = 0; i < n; ++i) {
while (deq[front] < i - k + 1) front++;
while (c[i] <= c[deq[back]] + s * (i - deq[back]) && back >= front) back--;
deq[++back] = i;
sum += 1ll * (c[deq[front]] * p[i]) + 1ll * s * (i - deq[front]) * p[i];
}
fout << sum;
return 0;
}