Cod sursa(job #1768536)

Utilizator geni950814Geni Geni geni950814 Data 1 octombrie 2016 04:58:57
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <iostream>
#include <cstdio>
#include <deque>
#include <vector>

using namespace std;
typedef long long ll;
vector<int> str;
deque<int> dq;

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