Cod sursa(job #626306)

Utilizator sebii_cSebastian Claici sebii_c Data 26 octombrie 2011 19:52:47
Problema Deque Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 0.58 kb
#include <stdio.h>
#define NMAX 10000

int N, K;
int A[NMAX], deque[NMAX];
int front, back;

int main()
{
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);
    int i;
    long long sum = 0;
    scanf("%d %d", &N, &K);
    front = 1, back = 0;
    for (i=1; i<=N; ++i)
	scanf("%d", &A[i]);
    
    for (i=1; i<=N; ++i) {
	while (front <= back && A[i] <= A[deque[back]])
	    --back;
	deque[++back] = i;
	
	if (deque[front] == i-K)
	    ++front;
	if (i >= K)
	    sum += A[deque[front]];
    }

    printf("%lld ", sum);
    return 0;
}