Cod sursa(job #679451)
Utilizator | Alexandru Cristian TheShadows | Data | 13 februarie 2012 11:51:06 |
---|---|---|---|
Problema | Deque | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include<stdio.h>
int st=-1,dr,v[5000010],d[5000010],k,n;
long long s=0;
void dreapta(int i)
{
while(st<=dr&&v[i]<=v[d[dr]])
dr--;
d[++dr]=i;
}
inline void stanga(int i)
{
if(d[st]==i-k)
st++;
}
int main()
{
FILE *in=fopen("deque.in","r"),*out=fopen("deque.out","w");
int i;
fscanf(in,"%d%d",&n,&k);
for(i=1;i<=n;i++)
fscanf(in,"%d",&v[i]);
for(i=1;i<=n;i++)
{
if(i>k)
stanga(i);
dreapta(i);
if(i>=k)
s+=v[d[st]];
}
fprintf(out,"%lld\n",s);
return 0;
}