Cod sursa(job #3120789)

Utilizator stefan2806Radulescu Stefan stefan2806 Data 8 aprilie 2023 16:10:59
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <deque>

using namespace std;

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

long long n, i, k, x, s;
deque < pair <int,int> > q;

int main()
{
    cin >> n >> k;
    cin >> x;
    q.push_back({ 1, x});
    if(k == 1)
        s = x;
    for(i = 2; i <= n; i++)
    {
        cin >> x;
        while(!q.empty() && x < q.back().second)
            q.pop_back();
        q.push_back({ i, x});
        if(i >= q.front().first + k)
            q.pop_front();
        if(i >= k)
            s += q.front().second;
        //cout << s << " ";
    }
    cout << s;
    return 0;
}