Cod sursa(job #2450063)

Utilizator ejoi2019Ejoi 2019 ejoi2019 Data 21 august 2019 18:32:12
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.59 kb
#include <cstdio>
#include <deque>

using namespace std;

int n, k;
deque <pair <int, int>> dq;
long long ans = 0;

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

  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    while (!dq.empty() && x <= dq.back().first) {
      dq.pop_back();
    }
    dq.push_back({x, i});
    if (i - dq.front().second + 1 > k) {
      dq.pop_front();
    }
    if (i >= k) {
      ans += dq.front().first;
    }
  }
  printf("%lld\n", ans);



  return 0;
}