Cod sursa(job #2041670)

Utilizator dragosQQCirtorosan Dragos dragosQQ Data 17 octombrie 2017 18:04:49
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define mx 5000001

using namespace std;

deque < pair<int,int> > coada;
int a[mx],k,suma;


int main (){
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    int i,n,x;
    cin>>n>>k;
    for (i=0; i<n; i++){
        cin>>x;
        while ((!coada.empty()) && (x<coada.back().first))
            coada.pop_back();
        coada.push_back({x,i});
        if (coada.front().second <= i-k) coada.pop_front();
        if (i >= k-1) suma+=coada.front().first;
    }
    cout<<suma;
    return 0;
}