Cod sursa(job #982455)
Utilizator | Taraban Dragos-Petru TarabanDragos | Data | 9 august 2013 11:48:08 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include<cstdio>
int n,k,i,j,p,u,d[5000001],v[5000001];
long long s;
FILE *f,*g;
int main(){
f=fopen("deque.in","r");
g=fopen("deque.out","w");
fscanf(f,"%d%d",&n,&k);
p=1;
u=0;
for(i=1;i<=n;i++){
fscanf(f,"%d",&v[i]);
}
for(i=1;i<=n;i++){
while(v[i]<v[d[u]] && u>=p){
u--;
}
d[++u]=i;
if(i>=k){
if(i-d[p]==k)
p++;
s+=v[d[p]];
}
}
fprintf(g,"%lld",s);
fclose(f);
fclose(g);
return 0;
}