Cod sursa(job #1299820)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 23 decembrie 2014 21:21:48
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <cstdio>
#include <deque>

using namespace std;

FILE *fin=freopen("deque.in","r",stdin);
FILE *fout=freopen("deque.out","w",stdout);

deque <int> d;
int n, k, v[5000000];
long long int Sum;

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1 ; i <= n ; ++i )
    {
        scanf("%d", &v[i]);
        while( !d.empty() && v[d.back()] > v[i] )
            {
                d.pop_back();
            }
        d.push_back(i);

        if( d[0] + k <= i )
            d.pop_front();

        if( i >= k )
            Sum += v[d[0]];
    }

    printf("%lld", Sum);

    return 0;
}