Cod sursa(job #1694231)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 24 aprilie 2016 22:55:29
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 100005;

struct PII{
    int x, y;
};

int main(void){
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    deque<PII> dk_max, dk_min;
    int n,k,t,ans=0;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; ++i){
        scanf("%d",&t);

        while(!dk_min.empty() && i-dk_min.front().y>=k) dk_min.pop_front();
        while(!dk_min.empty() && dk_min.back().x>=t) dk_min.pop_back();

        dk_min.push_back({t, i});

        if(i>=k)
            ans+=dk_min.front().x;
    }
    printf("%d",ans);
    return 0;
}