Cod sursa(job #2587290)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 22 martie 2020 16:39:52
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <cstdio>
#include <deque>
#include <vector>

using namespace std;
deque<int> deq;
vector<int> values;

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

  int N, K;
  scanf("%d%d", &N, &K);
  values.resize(N);
  long long answer = 0;
  for (int i = 0; i < N; ++i) {
    scanf("%d", &values[i]);

    while (!deq.empty() && values[deq.back()] > values[i])
      deq.pop_back();

    deq.push_back(i);

    while (!deq.empty() && i - deq.front() >= K)
      deq.pop_front();

    if (i >= K - 1)
      answer += values[deq.front()];
  }
  printf("%lld\n", answer);
  return 0;
}