Pagini recente » Cod sursa (job #1626597) | Cod sursa (job #2322394) | Cod sursa (job #401646) | Cod sursa (job #377820) | Cod sursa (job #374537)
Cod sursa(job #374537)
#include<cstdio>
int n,k,st,dr,j,sum,min;
int dq[5000001];
int v[5000001];
inline void stanga(int i)
{
if (dq[st]==i-k)
++st;
}
void dreapta (int i)
{
while(st<=dr && v[i]<=v[dq[dr]] )
--dr;
dq[++dr]=i;
}
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d", &n, &k);
for (j=1;j<=n;j++)
scanf("%d\n", &v[j]);
st=1;
dr=k;
for (j=1;j<k;j++)
{
stanga(j);
dreapta(j);
}
for (j=k;j<=n;j++)
{
stanga(j);
dreapta(j);
sum+=v[dq[st]];
}
printf("%d", sum);
return 0;
}