Cod sursa(job #2349754)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 20 februarie 2019 18:08:13
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <cstdio>
#include <deque>

using namespace std;

deque <long long> d1,d2;

int main()
{
    freopen("deque.in","r",stdin);
    freopen("deque.out","w",stdout);
    long long n,i,k,nr,s;
    cin>>n>>k;
    for(i=1;i<=k;i++)
    {
        cin>>nr;
        while(!d1.empty() && d1.back()>nr)
        {
            d1.pop_back();
            d2.pop_back();
        }
        d1.push_back(nr);
        d2.push_back(i);
    }
    s=d1.front();
    for(i=k+1;i<=n;i++)
    {
        cin>>nr;
        while(!d1.empty() && d1.back()>nr){
            d1.pop_back();
            d2.pop_back();
        }
        d1.push_back(nr);
        d2.push_back(i);
        while(!d1.empty() && d2.front()<i-k+1)
        {
            d1.pop_front();
            d2.pop_front();
        }
        s=s+d1.front();
    }
    cout<<s;
    return 0;
}