Cod sursa(job #2044373)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 21 octombrie 2017 09:42:25
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>
#include <queue>

using namespace std;
FILE *fin=fopen("deque.in","r");
FILE *fout=fopen("deque.out","w");

struct el{
    int val;
    int poz;
};

deque <el> DQ;
int n, k;
int s;

int main()
{
el y;
int x;
fscanf(fin,"%d %d",&n,&k);
for (int i=1;i<=n;i++)
    {
     fscanf(fin,"%d",&x);
     y.val=x;
     y.poz=i;
     while (!DQ.empty())
        {
         if (DQ.back().val>=y.val)
            DQ.pop_back();
            else break;
        }
     DQ.push_back(y);
     if (DQ.front().poz==i-k)
         DQ.pop_front();
     if (i>=k)
        s+=DQ.front().val;
    }
fprintf(fout,"%d\n",s);
fclose(fin);
fclose(fout);
return 0;
}