Pagini recente » Istoria paginii utilizator/enzo | Cod sursa (job #812466)
Cod sursa(job #812466)
#include <stdio.h>
#include <stdlib.h>
typedef struct Nr
{
int val, poz;
}nr;
nr c[5000001];
int main()
{
FILE *in = fopen("deque.in", "r"), *out = fopen("deque.out", "w");
int n, k, i, x, inc = 1, sf = 1;
long long sum = 0;
fscanf(in, "%d%d", &n, &k);
fscanf(in, "%d", &x);
c[1].val = x; c[1].poz = 1; sum += x;
for (i=2;i<=n;i++)
{
fscanf(in, "%d", &x);
while (x <= c[sf].val && sf >= inc) sf--;
c[++sf].val = x; c[sf].poz = i;
if (c[inc].poz + k <= i) inc++;
if (i > k) sum += c[inc].val;
}
fprintf(out, "%lld", sum);
return 0;
}