Cod sursa(job #1768196)

Utilizator geni950814Geni Geni geni950814 Data 30 septembrie 2016 14:57:59
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <cstdio>
#include <deque>
#include <vector>

using namespace std;
vector<int> str;
deque<int> dq;

int main() {
  freopen("deque.in", "r", stdin);
  freopen("deque.out", "w", stdout);
  int N, K, d;
  int min = 0;
  scanf("%d %d", &N, &K);
  scanf("%d", &d);
  str.push_back(d);
  dq.push_front(d); 
  for(int i = 1; i < N; i++) {
    scanf("%d", &d); 
    str.push_back(d);
    if(i >= K) {
      min += dq.front();
      if(str[i-K] == dq.front()) {
        dq.pop_front();
      }
    }
    if(dq.empty()) {
      dq.push_front(str[i]);
    } else {
      while(!dq.empty() && dq.back() > str[i]) {
        dq.pop_back();
      }
      dq.push_back(str[i]);
    }
  }
  min += dq.front();
  printf("%d", min);
  return 0;
}