Cod sursa(job #278955)
Utilizator | [email protected] Scorpion | Data | 12 martie 2009 17:02:36 |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.42 kb |
#include <iostream.h>
#include<fstream.h>
int deq[5000001],v[5000001];
int main()
{
int st=1,dr=0,n,i,k;
long long s=0;
ifstream f("date.in");
ofstream h("date.out");
f>>n>>k;
for(i=1;i<=n;i++)
f>>v[i];
for(i=1;i<=n;i++){
while(st<=dr && v[deq[dr]]>=v[i])
dr--;
deq[++dr]=i;
while(deq[st]<=i-k)
st++;
if(i>=k)
s+=v[deq[st]];
}
h<<s;
return 0;
}