Cod sursa(job #2475322)

Utilizator amalia.gemanGeman Aamalia amalia.geman Data 16 octombrie 2019 19:35:53
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#define N 5001
using namespace std;

int main()
{
    long long i,n,k;

    cin>>n>>k;

    long long a[N],s=0;
    for(i=1;i<=n;i++)
        cin>>a[i];



    int fronti=1,backi=0,C[N]; //coada vida
    //in coada vom memora pozitiile

    for(i=1;i<=n;i++)
    {
        //cat timp elementul curent este mai mic fata de elementele din coada, le vom scoate din coada
        while(fronti<=backi && a[i]<=a[C[backi]])backi--;
        //adaugam pozitia elementului curent in coada
        C[++backi]=i;

        //daca primul element nu mai face parte din nicio grupa
        if(C[fronti] == i-k)fronti++;


        //adaugam minimul la suma
        if(i>=k)s+=a[C[fronti]];
    }

    cout<<s;

    return 0;
}