Cod sursa(job #3350229)

Utilizator ungureanubogdanUngureanu Bogdan ungureanubogdan Data 6 aprilie 2026 15:38:44
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream>
#include <deque>

using namespace std;

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

int n, k;
int a[5000001];
deque<int> dq;

int main() {
    
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    int sum = 0;
    
    for(int i = 1; i <= n; ++i) {
        
        while(!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);

        while(dq.front() <= i - k) dq.pop_front();
        
        if(i >= k) {
            sum += a[dq.front()];
        }

    }

    cout << sum << '\n';

    return 0;
}