Cod sursa(job #2483705)

Utilizator stormy_weatherelena cristina stormy_weather Data 30 octombrie 2019 09:43:13
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<deque>
using namespace std;

int main() {

  #ifdef INFOARENA
  ifstream cin("deque.in");
  ofstream cout("deque.out");
  #endif

  int n, k;
  cin >> n >> k;

  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  vector<int> mini;
  deque<int> cand;

  for (int i = 0; i < n; i++) {
    while (!cand.empty() && a[cand.back()] > a[i])
      cand.pop_back();
    cand.push_back(i);

    if (i + 1 >= k) {
      mini.push_back(a[cand.front()]);
      if (cand.front() <= (i  + 1) - k)
        cand.pop_front();
    }
  }

  int64_t sum = 0;
  for (int i = 0; i < (int)mini.size(); i++) {
    sum += mini[i];
  }
  cout << sum << "\n";

  return 0;
}