Cod sursa(job #2587293)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 22 martie 2020 16:43:20
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 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]);
  for (int i = 0; i < N; ++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;
}