Cod sursa(job #311845)
Utilizator | Stoica Razvan-Andrei dorel | Data | 4 mai 2009 15:02:05 |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.5 kb |
#include<stdio.h>
#define N 5000001
int d[N],v[N],p,n,u,k;
void stanga (int i)
{
if (i-d[p]==k)
++p;
}
void dreapta (int i)
{
while (p<=u && v[i]<=v[d[u]])
--u;
d[++u]=i;
}
int main ()
{
int s,i;
freopen ("deque.in","r",stdin);
freopen ("deque.out","w",stdout);
p=1;
u=0;
for (i=1 ; i<=n ; ++i)
{
scanf ("%d",&v[i]);
}
u=0;
p=1;
s=v[d[p]];
for (i=1 ; i<=n ; ++i)
{
dreapta(i);
stanga(i);
if (i>=k)
s+=v[d[p]];
}
printf ("%d",s);
return 0;
}