Cod sursa(job #1597472)
Utilizator | Petru G petroo | Data | 12 februarie 2016 00:04:15 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <stdio.h>
#define MAX 5000001
int Vector[MAX], Deque[MAX];
int main(void)
{
int i, N, K, head = 1, tail = 0;
long long Sum = 0;
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
scanf("%d%d", &N, &K);
for (i = 1;i <= N;i++)
scanf( "%d", &Vector[i]);
for (i = 1;i <= N;i++)
{
while ( (head <= tail) && (Vector[i] <= Vector[Deque[tail]]))
tail--;
Deque[++tail] = i;
if (Deque[head] == i - K)
head++;
if (i >= K)
Sum += Vector[Deque[head]];
}
printf("%lld", Sum);
return 0;
}