Cod sursa(job #1796648)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 3 noiembrie 2016 17:33:07
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream f("deque.in");
ofstream g("deque.out");

int n, k, x;
long long sum = 0;

deque<pair<int, int>> d;

void insert_in_deque(int i, int x) {
  while (!d.empty() && d.back().second > x) {
    d.pop_back();
  }
  d.push_back(make_pair(i, x));
}

void remove_from_deque(int position) {
  while (!d.empty() && d.front().first < position - k + 1) {
    d.pop_front();
  }
}


int main() {
  f >> n >> k;

  for (int i = 1; i < k; ++i) {
    f >> x;
    insert_in_deque(i, x);
  }

  for (int i = k; i <= n; ++i) {
    f >> x;
    remove_from_deque(i);
    insert_in_deque(i, x);
    sum += d.front().second;
  }

  g << sum << "\n";

  f.close();
  g.close();
  return 0;
}