Pagini recente » Cod sursa (job #1703520) | Cod sursa (job #2310568) | Cod sursa (job #827604) | Cod sursa (job #2781883) | Cod sursa (job #893057)
Cod sursa(job #893057)
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <deque>
using namespace std;
#define Nmax 5000010
deque<int> D;
int N, K, V[Nmax];
long long Sum;
int main()
{
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int i;
scanf("%i %i", &N, &K);
for(i = 1; i <= N; ++ i) scanf("%i", &V[i]);
for(i = 1; i <= N; ++ i)
{
while(!D.empty() && V[D.back()] >= V[i]) D.pop_back();
D.push_back(i);
while(!D.empty() && D.front() <= i - K) D.pop_front();
if(D.size() && i >= K) Sum += 1LL * V[D.front()];
}
printf("%lld\n", Sum);
return 0;
}