Cod sursa(job #1576552)

Utilizator herbertoHerbert Mohanu herberto Data 22 ianuarie 2016 15:59:10
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
#include<deque>
using namespace std;

deque <int> d;
deque <int> poz;
int main(){
  FILE*fin=fopen("deque.in", "r");
  FILE*fout=fopen("deque.out", "w");
  int n, k, i, a;
  long long s;
  fscanf(fin, "%d%d", &n, &k);
  s=0;
  for(i=1; i<=n; i++){
    if(!d.empty() && i-poz.front()>=k){
      d.pop_front();
      poz.pop_front();
    }
    fscanf(fin, "%d", &a);
    while(!d.empty() && a<=d.back()){
      d.pop_back();
      poz.pop_back();
    }
    d.push_back(a);
    poz.push_back(i);
    if(i>=k)
      s+=d.front();
//    printf("%d %d\n", i, s);
  }
  fprintf(fout, "%lld", s);
  fclose(fin);
  fclose(fout);
  return 0;
}