Cod sursa(job #3309863)

Utilizator hrib_the_slothAndreea Pasca hrib_the_sloth Data 10 septembrie 2025 04:57:21
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i8;

int main() {
  ifstream cin("deque.in");
  ofstream cout("deque.out");
  int n, k;
  cin >> n >> k;
  vector<int> v(n + 2, 0);
  for (int i = 1; i <= n; i++) {
    cin >> v[i];
  }

  deque<int> d;
  int res = 0;
  for (int i = 1; i <= n; i++) {
    while (!d.empty() && v[i] <= v[d.back()]) {
      d.pop_back();
    }
    d.push_back(i);

    if (i >= k) {
      if (d.front() <= i - k) {
        d.pop_front();
      }
      res += v[d.front()];
    }
  }
  cout << res << "\n";
}