Cod sursa(job #1529496)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 20 noiembrie 2015 22:57:04
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <deque>
#include <algorithm>

#define value first
#define position second
using namespace std;

deque <pair <int, int> > Deque; int N, K, X; long long S;

int main () {

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

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

    for (int i = 1; i <= N; i ++) {
        scanf ("%d", &X);

        while (!Deque.empty() && X <= Deque.back().value)
            Deque.pop_back();
        Deque.push_back(make_pair(X, i));

        if (Deque.front().position == i - K)
            Deque.pop_front();

        if (i >= K)
            S += Deque.front().value;
    }

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

    return 0;
}