Cod sursa(job #672543)
Utilizator | Data | 2 februarie 2012 16:01:04 | |
---|---|---|---|
Problema | Deque | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.48 kb |
#include<stdio.h>
struct DEQUE {int a,i;};
DEQUE q[5000005];
int p,u,i;
void adaugare(int x)
{
while(u)
{
if(q[u].a<x)
break;
u--;
}
q[++u].a=x;
q[u].i=i;
}
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int n,k,x;p=1;u=0;
long long s=0;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
adaugare(x);
if(q[u].i-q[p].i==k)
p++;
if(i>=k)
s=s+q[p].a;
}
printf("%lld\n",s);
return 0;
}