Pagini recente » Borderou de evaluare (job #3203796) | Borderou de evaluare (job #1235949) | Cod sursa (job #2732223)
#include <fstream>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int N, K, A[5000001], deq[5000001], Suma, Front, Back;
int main(){
Suma=0;
fin>>N>>K;
for(int i=1; i<=N; i++){
fin>>A[i];
}
Front=1; Back=0;
for(int i=1; i<=N; i++){
while(Front<=Back && A[i]<=A[deq[Back]]){
Back--;
}
Back++;
deq[Back]=i;
if(deq[Front]==i-K) Front++;
if(i>=K) Suma=Suma+A[deq[Front]];
}
fout<<Suma;
return 0;
}