Cod sursa(job #715700)

Utilizator Sm3USmeu Rares Sm3U Data 17 martie 2012 17:03:21
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <deque>
#define nMax 5000010

using namespace std;

deque <int> deq;
int a[nMax];
int s;
int k;
int n;

void adauga(int x)
{
    while (!deq.empty() && a[deq.front()] >= a[x]){
        deq.pop_front();
    }
    while (!deq.empty() && deq.back() + k <= x){
        deq.pop_back();
    }
    deq.push_front(x);
   // s += a[deq.back()];
}

void citire()
{
    scanf ("%d %d", &n, &k);
    for (int i = 0; i < k; ++ i){
        scanf ("%d", &a[i]);
        adauga(i);
    }
    s += a[deq.back()];
    for (int i = k; i < n; ++ i){
        scanf ("%d", &a[i]);
        adauga(i);
        s += a[deq.back()];
    }
}

int main()
{
    freopen ("deque.in", "r", stdin);
    freopen ("deque.out", "w", stdout);
    citire();
    printf ("%d\n", s);

    return 0;
}