Cod sursa(job #274264)

Utilizator zerobaratalexandra zerobarat Data 9 martie 2009 16:20:44
Problema Deque Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.39 kb
#include<fstream.h>
# define max 507
ifstream fin("deque.in");
ofstream fout("deque.out");

long n,k,p,sf,a[max],d[max];
long long s;

int main()
{long i;

fin>>n>>k;
for(i=1;i<=n;i++)fin>>a[i];

p=sf=1;
for(i=1;i<=n;i++)
{
while(p<=sf&&a[i]<=a[d[sf]])sf--;

d[++sf]=i;

if(d[p]==i-k)p++;

if(i>=k) s+=a[d[p]];
}

fout<<s<<'\n';

fin.close();
fout.close();
return 0;
}