Cod sursa(job #1066742)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 25 decembrie 2013 15:37:35
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.49 kb
#include<fstream>
#include <deque>

using namespace std;


 int a[5000010],k,n,i;


main(){
  ifstream fin("deque.in");
  ofstream fout("deque.out"); 
  
 long long s=0;

  fin>>n;fin>>k;
  std::deque<int> fifth; 
  for(i=1;i<=n;++i){
  	fin>>a[i];
	while(!fifth.empty() && a[fifth.back()]>=a[i])fifth.pop_back(); 	
 	fifth.push_back(i); 	
 	if(fifth.front()==i-k)fifth.pop_front();
 	if(i-k>=0)s+=a[fifth.front()]; 
  }
 
 
 
  fout<<s;
    fin.close(); fout.close();
  
}