Cod sursa(job #2263237)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 18 octombrie 2018 14:55:27
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <deque>

using namespace std;

deque<int>v;
int s[5000005];

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

  int n, m, k;

  scanf( "%d%d", &n, &m );

  for( int i=1;i<=n;i++ )
    scanf( "%d", &s[i] );

  v.push_back(s[1]);

  for( int i=2;i<=m;i++ )
  {
    while( !v.empty() && s[i]<v.back() )
      v.pop_back();

    v.push_back(s[i]);
  }

  int sum=v.front();

  for( int i=m+1;i<=n;i++ )
  {
    if( s[i-m]==v.front() )
      v.pop_front();

    while( !v.empty() && s[i]<v.back() )
      v.pop_back();

    v.push_back(s[i]);

    sum+=v.front();
  }

  printf( "%d", sum );

  return 0;
}