Cod sursa(job #734465)

Utilizator a08iAndrei Ionescu a08i Data 14 aprilie 2012 12:30:52
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<iostream>
#include<deque>
#include<cstdio>
#include<vector>

using namespace std;

int main()
{

  freopen("deque.in", "r", stdin);
  freopen("deque.out", "w", stdout);

  int N, K, x;
  int total = 0;

  scanf("%d %d", &N, &K);

  deque< pair<int,int> > DQ;

  for(int i=0; i<N; i++)
  {
    scanf("%d", &x);
    while(!DQ.empty() && x <= DQ.back().first)
    {
      DQ.pop_back();
    }
    DQ.push_back(make_pair(x,i));


    if(DQ.front().second <= i-K)
    {
      DQ.pop_front();
    }
    if(i >= K-1)
    {
      total += DQ.front().first;
    }
  }

  printf("%d", total);

  return 0;
}