Pagini recente » Cod sursa (job #2428543) | Cod sursa (job #2563487) | Cod sursa (job #3280948) | Cod sursa (job #1755359) | Cod sursa (job #3261353)
#include <stdio.h>
#define N 100000
int dq[N], v[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++;
int st = 0, dr = -1;
long long suma = 0;
for (int i = 0; i < n; i++)
{
int c;
fscanf(in, "%d%d", &v[i], &c);
if (st <= dr && dq[st] == i - k)
{
st++;///eliminam branza stricata
}
while (st <= dr && v[i] <= v[dq[dr]] + s * (i - dq[dr]))
{
dr--;
}
dq[++dr] = i;
suma += (long long)c * (v[dq[st]] + s * (i - dq[st]));
}
fprintf(out, "%lld\n", suma);
fclose(in);
fclose(out);
return 0;
}