Cod sursa(job #1311111)

Utilizator radu_uniculeu sunt radu radu_unicul Data 7 ianuarie 2015 19:01:31
Problema Deque Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <stdio.h>

#define maxn 5000010
#define inf 1000000000

int N, K;
int A[maxn];
long long Sum;

int main()
{
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);

    int i, j, p = 0, best;

    scanf("%d %d ", &N, &K);

    for (i = 1; i <= N; i++) scanf("%d ", &A[i]);

    best = inf;
    for (i = 1; i <= N; i++)
    {
        if (A[i] <= best) best = A[i], p = i;

        if (p <= i-K)
        {
            best = inf, p = 0;
            for (j=0; j<K; j++)
                if (A[i-j] < best) best = A[i-j], p = i-j;
        }

        if (i >= K) Sum += best;
    }

    printf("%lld\n", Sum);

    return 0;
}