Cod sursa(job #1758865)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 17 septembrie 2016 23:44:14
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>
#include <deque>
using namespace std;
struct ABC{
  int val, poz;
};
deque<ABC>d;
int main(){
  freopen("deque.in", "r", stdin);
  freopen("deque.out", "w", stdout);
  int n, k, i, x;
  long long s = 0;
  ABC aux;
  scanf("%d%d", &n, &k);
  for (i = 1; i <= k; i ++){
    scanf("%d", &x);
    while (!d.empty() && d.back().val >= x)
      d.pop_back();
    aux.val = x;
    aux.poz = i;
    d.push_back(aux);
  }
  s = d.front().val;
  for (i = k + 1; i <= n; i ++){
    scanf("%d", &x);
    while (!d.empty() && d.back().val >= x)
      d.pop_back();
    aux.val = x;
    aux.poz = i;
    d.push_back(aux);
    if (d.front().poz == i - k)
      d.pop_front();
    s += d.front().val;
  }
  printf("%lld\n", s);
  return 0;
}