Cod sursa(job #2233708)

Utilizator danielsociuSociu Daniel danielsociu Data 24 august 2018 09:59:39
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <fstream>
std::ifstream cin("deque.in");
std::ofstream cout("deque.out");
#define maxn 5000002
int v[maxn], dequ[maxn], N,K;
int main()
{
    int SUM=0,Front=1,Back=0;
    cin>>N>>K;
    for(int i=1;i<=N;i++){
        cin>>v[i];
    }
    for(int i=1;i<=N;i++){
        while(Front<=Back&&v[i]<=v[dequ[Back]]){
            Back--;
        }

        dequ[++Back]=i;

        if(i-K==dequ[Front]){
            Front++;
        }
        if(i>=K){
            SUM+=v[dequ[Front]];
        }
    }
    cout<<SUM;
}