Pagini recente » Cod sursa (job #2611941) | Cod sursa (job #3190109) | Cod sursa (job #2726246) | Cod sursa (job #2063392) | Cod sursa (job #1803713)
#include <iostream>
#include <cstdio>
#include <deque>
#define NMAX 5000005
using namespace std;
int a[NMAX], n, k;
long long s;
deque<int> D;
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 <= k - 1; i++)
{
while(!D.empty() && a[i] <= a[D.back()])
D.pop_back();
D.push_back(i);
}
for(int i = k; i <= n; i++)
{
while(!D.empty() && a[i] <= a[D.back()])
D.pop_back();
D.push_front(i);
while(!D.empty() && i >= D.back() + k)
D.pop_back();
if(!D.empty())
s += a[D.back()];
}
printf("%lld", s);
return 0;
}