Cod sursa(job #1066708)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 25 decembrie 2013 14:37:13
Problema Deque Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include<fstream>
#include <deque>

using namespace std;





main(){
  ifstream fin("deque.in");
  ofstream fout("deque.out"); 
  
  signed long long  a[150000],s=0,k,n,i;
  fin>>n;fin>>k;
  std::deque<signed long long> 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();
  
}