Cod sursa(job #3373477)

Utilizator markymrkKemenes Mark markymrk Data 7 noiembrie 2026 10:41:03
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
#define int long long
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; cin >> n >> k;
    for (int i = 1; i <= n ;++i) {
        cin >> 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()];
    }
    cout << sum << "\n";

}