Pagini recente » Cod sursa (job #2174728) | Cod sursa (job #1508710)
#include <cstdio>
#include <deque>
using namespace std;
int n, k, a[5000010];
long long sum;
deque < int > C;
int main()
{
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int i;
scanf("%d %d ", &n, &k);
for (i=1; i<=n; i++) scanf("%d ", &a[i]);
for (i=1; i<=n; i++)
{
while (C.size() && a[i]<=a[C.back()])
C.pop_back();
C.push_back(i);
if (C.front()==i-k) C.pop_front();
if (i>=k) sum+=a[C.front()];
}
printf("%lld\n", sum);
return 0;
}