Cod sursa(job #2743165)

Utilizator lucriLuchian Cristian lucri Data 22 aprilie 2021 17:27:23
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
deque <pair<long long,long long>>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;
}