Cod sursa(job #2730214)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 25 martie 2021 22:29:10
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.53 kb
#include <bits/stdc++.h>
using namespace std;
long long n, k, i, sum;
struct elem
{
    long long val;
    long long poz;
}x;
deque <elem> Q;
int main()
{
    cin >> n >> k;
    for(i = 1; i <= n; i ++)
    {
        cin >> x.val;
        x.poz = i;
        while(!Q.empty() && Q.back().val >= x.val)
            Q.pop_back();
        Q.push_back(x);
        if(i < k)continue;
        while(Q.front().poz  <= i - k)
            Q.pop_front();
        sum = sum + Q.front().val;
    }
    cout << sum;
    return 0;
}