Cod sursa(job #2667305)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 3 noiembrie 2020 12:12:21
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.49 kb
#include <iostream>
#include <fstream>
#include <deque>

std::deque<std::pair<int64_t, int64_t>> dq;

int main() {
  std::ifstream in("deque.in");
  std::ofstream out("deque.out");

  int64_t n, k, a, s = 0;
  in >> n >> k;

  for (int i = 1; i <= n; ++i) {
    in >> a;

    while (!dq.empty() && dq.back().first > a)
      dq.pop_back();

    dq.emplace_back(a, i);

    if (dq.front().second <= i - k)
      dq.pop_front();

    if (i >= k)
      s += dq.front().first;
  }

  out << s;

  return 0;
}