Pagini recente » Cod sursa (job #1204831) | Cod sursa (job #3274046) | Cod sursa (job #2652271) | Cod sursa (job #3190935) | Cod sursa (job #772018)
Cod sursa(job #772018)
/*
Dequeue.
*/
#include <iostream>
#include <stdio.h>
#define MAXN 5000000
int n, k;
int a[MAXN], dequeue[MAXN];
int front, back;
long long suma_minime;
void calculeaza_suma () {
front = 1;
back = 0;
for (int i = 1; i <= n; i++) {
while (front <= back && a[i] <= a[dequeue[back]])
back--;
back++;
dequeue[back] = i;
if (dequeue[front] == i - k)
front++;
if (i >= k)
suma_minime += a[dequeue[front]];
}
}
int main () {
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int i;
scanf("%d %d", &n, &k);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
calculeaza_suma();
printf("%lld\n", suma_minime);
return 0;
}