Cod sursa(job #311865)
Utilizator | Matei Ionita nemultumitul | Data | 4 mai 2009 15:33:11 |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <stdio.h>
long long d[5000000],v[5000000];
int p,u,n,K;
void stanga(int x)
{
if (x-d[p]>=K)
p++;
}
void dreapta(int x)
{
while (p<=u&&v[x]<=v[d[u]])
u--;
d[++u]=x;
}
int main()
{
freopen ("deque.in","r",stdin);
freopen ("deque.out","w",stdout);
int x;
long long s=0;
scanf("%d%d",&n,&K);
for (x=0;x<K;++x)
{
scanf("%d",&v[x]);
dreapta(x);
}
s=v[d[p]];
for(x=K;x<n;++x)
{
scanf("%d",&v[x]);
stanga(x);
dreapta(x);
s+=v[d[p]];
}
printf("%d",s);
return 0;
}