Pagini recente » Cod sursa (job #1608266) | Cod sursa (job #31806) | Cod sursa (job #2932744) | Cod sursa (job #1483873) | Cod sursa (job #2887290)
#include <fstream>
int c[100010], p[100010];
int deq[100010];
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 && back >= front) 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;
}