Cod sursa(job #3310437)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 13 septembrie 2025 23:03:39
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <deque>
using namespace std;

const int NMAX = 5000005;

int v[NMAX];

int main() {
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);


    int n, k;
    scanf("%d %d", &n, &k);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }

    deque<int> dq;
    for (int i = 1; i <= k; i++) {
        while (!dq.empty() && v[dq.back()] >= v[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    int sume_minime = v[dq.front()];
    for (int i = k + 1; i <= n; i++) {
        while (!dq.empty() && v[dq.back()] >= v[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        if (i - k + 1 > dq.front()) {
            dq.pop_front();
        }
        if (!dq.empty()) {
            sume_minime += v[dq.front()];
        }
    }

    printf("%d ",sume_minime);


    return 0;
}