Cod sursa(job #1357556)

Utilizator superman_01Avramescu Cristian superman_01 Data 23 februarie 2015 23:12:34
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <algorithm>
#include <vector>
#include <fstream>
#include <cstring>
#include <deque>

#define NMAX 5000005

using namespace std;

ifstream in ( "deque.in" );
ofstream out ( "deque.out" );
int N  ,  K;
deque < int > Q;
int Answer;
int v[NMAX];


int main ( void ){
   int i , j ;
   in >> N >> K ;
   for ( i = 1 ; i <= N ; ++i )
      in >> v[i];
   for ( i = 1 ; i <= N ; ++i ){
      while ( v[i] < v[Q.back()] and Q.size() )
         Q.pop_back();
    Q.push_back(i);
    while ( i-Q.front() > K)
    Q.pop_front();
    if( i >= K )
    Answer += v[Q.front()];
   }
   out << Answer << "\n";
  return 0 ;
}