Cod sursa(job #260584)
Utilizator | Data | 17 februarie 2009 11:31:26 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <stdio.h>
int n,k,lol[5000005], poz[5000005];
long long S;
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int p,u;
scanf("%d %d",&n,&k);
for (int i=1;i<=n;i++)
scanf("%d",&lol[i]);
p=1;u=0;
for (int i=1;i<=n;i++)
{
while (lol[i]<=lol[poz[u]] && u>=p)
u--;
poz[++u]=i;
if (poz[p]==i-k)
p++;
if (i>=k)
S+=lol[poz[p]];
}
printf("%lld\n",S);
return 0;
}