Pagini recente » Inundatie | Cod sursa (job #3292271) | Monitorul de evaluare | Rating BadeaTheodorIulian (badeatheodor) | Cod sursa (job #672574)
Cod sursa(job #672574)
#include<stdio.h>
int n,k,i,p,u,a;
long long min;
struct tudi
{
int i,v;
};
tudi dq[5000001];
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d",&n,&k);
p=1;
u=1;
scanf("%d",&a);
dq[p].v=a;
dq[p].i=1;
for(i=2;i<=n;i++)
{
scanf("%d",&a);
if(a>dq[u].v)
{dq[++u].v=a; dq[u].i=i;}
if(a<dq[u].v)
{
while(a<dq[u].v&&p<=u)
{
u--;
}
dq[++u].v=a;
dq[u].i=i;
}
if(dq[u].i-dq[p].i+1>k)
p++;
if(i>=k)
min=min+dq[p].v;
}
printf("%lld",min);
return 0;
}