Cod sursa(job #3350225)

Utilizator ungureanubogdanUngureanu Bogdan ungureanubogdan Data 6 aprilie 2026 15:35:53
Problema Deque Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <deque>

using namespace std;

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

int n, k;
int a[1001];
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 <= k; ++i) {
        while(!dq.empty() && a[dq.back()] > a[i]) dq.pop_back();
        dq.push_back(i);
    }
    sum += a[dq.front()];

    for(int i = k + 1; i <= n; ++i) {
        while(dq.front() <= i - k) dq.pop_front();

        while(!dq.empty() && a[dq.back()] > a[i]) dq.pop_back();
        dq.push_back(i);
        
        sum += a[dq.front()];

    }

    cout << sum << '\n';

    return 0;
}