Pagini recente » Cod sursa (job #1454500) | Cod sursa (job #599719) | Profil Deew9 | Cod sursa (job #979832) | Cod sursa (job #978539)
Cod sursa(job #978539)
#include<stdio.h>
#include<deque>
#define NMAX 5000007
using namespace std;
deque < int > Deq;
int n, k, Sum;
int a[NMAX];
int main(){
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
scanf("%d %d", &n, &k);
for(int i = 1; i <= n ; ++ i)
scanf("%d", &a[i]);
for(int i = 1; i <= n; ++ i){
while(! Deq.empty() && a[Deq.back()] > a[i])
Deq.pop_back();
Deq.push_back(i);
while(! Deq.empty() && Deq.front() < i - k + 1 && i >= k)
Deq.pop_front();
if(i >= k && !Deq.empty())
Sum += a[Deq.front()];
}
printf("%d", Sum);
return 0;
}