Cod sursa(job #1066696)

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

using namespace std;





main(){
  ifstream fin("deque.in");
  ofstream fout("deque.out"); 
  int k,n,i,a[150000],s=0;
  fin>>n;fin>>k;
  std::deque<int> fifth; 
  for(i=1;i<=n;++i){
  	fin>>a[i];  
  }
 /* for(i=1;i<=n;++i){
  	fin>>a;
  	fifth.push_back (a);
  	fifth.pop_front();
  	min=INF;
  	for (std::deque<int>::iterator it = fifth.begin(); it!=fifth.end(); ++it)
  if(*it<min)min=*it ;
  	s+=min;
  }*/
 for(i=1;i<=n;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();
  
}