Pagini recente » Cod sursa (job #1347857) | Cod sursa (job #693590) | Cod sursa (job #1336644) | Cod sursa (job #1397048) | Cod sursa (job #2129558)
#include <cstdio>
#include <deque>
#include <iostream>
using namespace std;
#define NMAX 5000002
int sir[NMAX];
deque<int> pos;
int n, k;
long long sum;
void calc_min(){
pos.push_back(1);
for(int i = 1; i <= n; ++i){
while(!pos.empty() && sir[pos.back()] >= sir[i])
pos.pop_back();
if(!pos.empty() && i - pos.front() >= k && i >= k)
pos.pop_front();
if(!pos.empty())
sum += (long long)sir[pos.back()];
pos.push_back(i);
}
printf("%lld", sum);
}
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", &sir[i]);
calc_min();
return 0;
}