Cod sursa(job #2832472)

Utilizator NeuerRaducu Ioan Stefan Neuer Data 13 ianuarie 2022 19:58:50
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
///#include <iostream>
#include <fstream>
#include <deque>

using namespace std;
typedef long long ll;

ifstream cin("deque.in");
ofstream cout("deque.out");

struct elem
{
    ll val, pos;
};

deque <elem> dq;
ll sum, var, n, k;

void add2deq(elem e)
{
    while(!dq.empty() && dq.back().val>=e.val)
        dq.pop_back();
    dq.push_back(e);
}

int main()
{
    cin>>n>>k;
    for(int i=1; i<=k; i++) {
        cin>>var;
        add2deq({var, i});
    }
    sum += dq.front().val;
    for(int i=k+1; i<=n; i++) {
        cin>>var;
        add2deq({var, i});
        while(dq.front().pos<=i-k) dq.pop_front();
        sum += dq.front().val;
    }
    cout<<sum;
    return 0;
}