Cod sursa(job #2532186)

Utilizator anabatAna Batrineanu anabat Data 27 ianuarie 2020 15:10:16
Problema Deque Scor 25
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 5000000

int v[NMAX+1], deque[NMAX+1];

int inceput,sfarsit;

void pop_front(){
  inceput++;
}
void push_back(int x){
  deque[sfarsit]=x;
  sfarsit++;
}
void pop_back(){
  sfarsit--;
}
char empty(){
  return(inceput>=sfarsit);
}
int main()
{
  FILE *fin,*fout;
  fin=fopen("deque.in","r");
  fout=fopen("deque.out","w");

  int n,k,i,S=0;
  fscanf(fin,"%d%d",&n,&k);
  for(i=1;i<=n;i++){
    fscanf(fin,"%d",&v[i]);
  }
  for(i=1;i<=n;i++){
    if(i>k)
      S+=v[deque[inceput]];
    if(deque[inceput]<=i-k){
      pop_front();
    }
    while(!empty()&&v[i]<v[deque[sfarsit-1]]&&i!=1){
      pop_back();
    }
    push_back(i);
  }
  S+=v[deque[inceput]];
  fprintf(fout,"%d",S);

  fclose(fin);
  fclose(fout);
  return 0;
}