Cod sursa(job #3373502)

Utilizator markymrkKemenes Mark markymrk Data 7 noiembrie 2026 10:52:34
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Nmax = 5e6 + 5;
int arr[Nmax];
deque <int> dq;
char buf[1 << 16];
int pos = 1 << 16;
char getC() {
    if (pos == (1 << 16)) {
        fread(buf, 1, 1 << 16, stdin);
        pos = 0;
    }
    return buf[pos++];
}

int readInt() {
    char c = getC();
    while (c != '-' && (c < '0' || c > '9')) c = getC();
    int sgn = 1;
    if (c == '-') { sgn = -1; c = getC(); }
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getC();
    }
    return x * sgn;
}

signed main() {
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);
    int n, k;
    n = readInt();
    k = readInt();
    for (int i = 1; i <= n ;++i) {
        arr[i] = readInt();
    }
    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()];
    }
    cout << sum << "\n";

}