Cod sursa(job #2743168)

Utilizator lucriLuchian Cristian lucri Data 22 aprilie 2021 17:29:16
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
deque <pair<int,int>>a;
long long n,x,s,k;
int main()
{
    in>>n>>k;
    for(int i=1;i<k;++i)
    {
        in>>x;
        while(a.empty()!=true&&x<a.back().first)
            a.pop_back();
        a.push_back({x,i});
    }
    for(int i=k;i<=n;++i)
    {
        in>>x;
        while(a.empty()!=true&&x<a.back().first)
            a.pop_back();
        a.push_back({x,i});
        s+=a.front().first;
        if(a.front().second==i-k+1)
            a.pop_front();
    }
    out<<s;
    return 0;
}