Cod sursa(job #2233707)

Utilizator danielsociuSociu Daniel danielsociu Data 24 august 2018 09:56:20
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.5 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;
}