Cod sursa(job #2759382)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 17 iunie 2021 14:40:32
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 5000003;

int n,k,s;
int v[NMAX];
deque<int>q;

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",&v[i]);
        while(!q.empty() && v[i] < v[q.back()]){
            q.pop_back();
        }
        q.push_back(i);
        if(i-q.front()>=k){
            q.pop_front();
        }
        if(i>=k){
            s+=v[q.front()];
        }
    }
    printf("%d\n",s);

    return 0;
}