Cod sursa(job #1207946)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 14 iulie 2014 12:49:48
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <deque>
#include <iostream>
using namespace std;
FILE *f=fopen("deque.in","r");
FILE *g=fopen("deque.out","w");
deque <int> q,p;
long long sum;
int n,k,x;

int main()
{int i,j;
fscanf(f,"%d %d",&n,&k);
for (i=1;i<=k;i++) {fscanf(f,"%d",&x);
                    while (!q.empty()&&x<q.back()) {q.pop_back();
                                                    p.pop_back();}
                    q.push_back(x);
                    p.push_back(i);
                    }
sum+=q.front();
for (i=k+1;i<=n;i++) {if (!q.empty()&&i-p.front()==k) {p.pop_front();
                                                       q.pop_front();}

                      fscanf(f,"%d",&x);
                      while (!q.empty()&&x<q.back()) {q.pop_back();
                                                      p.pop_back();}
                      q.push_back(x);
                      p.push_back(i);


                      sum+=q.front();
                      }
fprintf(g,"%d\n",sum);
return 0;
}