Pagini recente » Cod sursa (job #2742313) | Cod sursa (job #2747731) | Cod sursa (job #1145409) | abac | Cod sursa (job #3204391)
#include <stdio.h>
#include <stdlib.h>
#define N 100000
int cost[N], dq[N];
int main()
{
FILE *in, *out;
in = fopen("branza.in", "r");
out = fopen("branza.out", "w");
int n, s, k;
fscanf(in, "%d%d%d", &n, &s, &k);
k++;
long long sum = 0;
int st = 0, dr = -1;
for (int i = 0; i < n; i++)
{
int cantitate;
fscanf(in, "%d%d", &cost[i], &cantitate);
///cat timp dq e e nevid si v[i] e mai bun sau egal cu cel mai prost din dq
while (st <= dr && cost[i] <= cost[dq[dr]] + (i - dq[dr]) * s)
{
dr--;///elimin din dreapta
}
if (st <= dr && dq[st] == i - k)
{
st++;///elimin din stanga
}
dq[++dr] = i;
sum += (long long)cantitate * (cost[dq[st]] + (i - dq[st]) * s);
}
fprintf(out, "%lld\n", sum);
fclose(in);
fclose(out);
return 0;
}