Cod sursa(job #1758868)

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