Cod sursa(job #3185515)

Utilizator SorinBossuMarian Sorin SorinBossu Data 19 decembrie 2023 11:38:01
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <iostream>
#include <fstream>
#include <deque>


std::ifstream in("file.in");
std::ofstream out("file.out");
int n, k;

int r = 0;
std::deque<std::pair<int, int>> dq;

int main()
{
    in >> n >> k;
    for ( int i = 1, x; i <= n; ++i )
    {
        in >> x;
        while ( !dq.empty() and dq.front().second < i - k + 1 )
          dq.pop_front();
        while ( !dq.empty() and dq.back().first >= x )
          dq.pop_back();
        dq.emplace_back(x, i);

        if ( i >= k )
            r+= dq.front().first;
    }

    out << r;
    return 0;
}