Cod sursa(job #3369707)

Utilizator radu_alexRadu Hopartean radu_alex Data 21 octombrie 2026 19:45:37
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb

#include <fstream>
#include <deque>
#include <vector>

std::ifstream in("deque.in");
std::ofstream out("deque.out");

int n,k,ans = 0;
std::vector<int>v;
std::deque<int>dq;

int main(void) {

    in >> n >> k;
    v.resize(n);

    for(int i = 0 ; i < n ; i ++ ) {
        in >> v[i];
    }

    for(int i = 0 ; i < n ; i ++ ) {
        
        while(!dq.empty() && dq.front() <= i-k) {
            dq.pop_front();
        }

        while(!dq.empty() && v[i] <= v[dq.back()]) {
            dq.pop_back();
        }

        dq.push_back(i);

        if(i >= k-1) {
            ans += v[dq.front()];
            // out << v[dq.front()] << " ";
        }
    }

    out << ans;

    return 0;
}