Pagini recente » Cod sursa (job #2153255) | Cod sursa (job #1138252) | Cod sursa (job #2217419) | Cod sursa (job #2271384) | Cod sursa (job #311852)
Cod sursa(job #311852)
#include<stdio.h>
#define N 5000001
int d[N],v[N],p,n,u,k;
void stanga (int i)
{
if (i-d[p]==k)
++p;
}
void dreapta (int i)
{
while (p<=u && v[i]<=v[d[u]])
--u;
d[++u]=i;
}
int main ()
{
int i;
long long s;
freopen ("deque.in","r",stdin);
freopen ("deque.out","w",stdout);
p=1;
u=0;
scanf ("%d%d",&n,&k);
for (i=1 ; i<=n ; ++i)
{
scanf ("%d",&v[i]);
}
u=0;
p=1;
s=v[d[p]];
for (i=1 ; i<=n ; ++i)
{
dreapta(i);
stanga(i);
if (i>=k)
s+=v[d[p]];
}
printf ("%lld",s);
return 0;
}