Cod sursa(job #1778153)

Utilizator tgm000Tudor Mocioi tgm000 Data 13 octombrie 2016 15:50:10
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<cstdio>
#include<deque>
using namespace std;
deque <int> d1;
deque <int> d2;
int main(){
  int n,k,i,a;
  long long s;
  freopen("deque.in","r",stdin);
  freopen("deque.out","w",stdout);
  scanf("%d%d",&n,&k);
  s=0;
  for(i=1;i<=n;i++){
      scanf("%d",&a);
      while(!d1.empty()&&a<d1.back()){
        d1.pop_back();
        d2.pop_back();
      }
      d1.push_back(a);
      d2.push_back(i);
      if(i>=k){
          while(!d1.empty()&&d2.back()-d2.front()>=k){
              d1.pop_front();
              d2.pop_front();
          }
          s=s+d1.front();
      }
  }
  printf("%lld",s);
  return 0;
}