Cod sursa(job #3373491)

Utilizator markymrkKemenes Mark markymrk Data 7 noiembrie 2026 10:48:01
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 5e6 + 5;
int arr[Nmax];
deque <int> dq;
signed main() {
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    for (int i = 1; i <= n ;++i) {
        scanf("%d", &arr[i]);
    }
    int sum = 0;
    for (int i = 1; i <= k; ++i) {
        while (!dq.empty() && arr[dq.front()] >= arr[i]) {
            dq.pop_front();
        }
        dq.push_front(i);
    }
    sum += arr[dq.back()];
    for (int i = k + 1; i <= n; ++i) {
        while (!dq.empty() && arr[dq.front()] >= arr[i]) {
            dq.pop_front();
        }
        dq.push_front(i);
        if (dq.back() == i - k) {
            dq.pop_back();
        }
        sum += arr[dq.back()];
    }
    printf("%d", sum);

}