Cod sursa(job #1804049)

Utilizator AdrianGotcaAdrian Gotca AdrianGotca Data 12 noiembrie 2016 10:26:25
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <deque>
#include <fstream>

using namespace std;

deque <int> D;
int a[5000005],n,k;
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",&a[i]);
    }
    for (int i=1;i<=k;i++){
        while (!D.empty()&&a[D.back()]>a[i]){
            D.pop_back();
        }
        D.push_back(i);
    }
    int s=0;
    for (int i=k+1;i<=n;i++){
        s+=a[D.front()];
        if (D.front()<=i-k){
            D.pop_front();
        }
        while (!D.empty()&&a[D.back()]>a[i]){
            D.pop_back();
        }
        D.push_back(i);
    }
    s+=a[D.front()];
    printf("%d",s);
}