Pagini recente » Cod sursa (job #624156) | Cod sursa (job #1171070) | Cod sursa (job #2919068) | Cod sursa (job #257652) | Cod sursa (job #2887282)
#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 += c[deq[front]] * p[i] + s * (i - deq[front]) * p[i];
}
fout << sum;
return 0;
}