Pagini recente » Cod sursa (job #196775) | Borderou de evaluare (job #2456265) | Cod sursa (job #2597905) | Cod sursa (job #2185316) | Cod sursa (job #2557723)
#include <bits/stdc++.h>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
int n,k;
int a[5000001];
int minim[5000001];
int coada[5000001],last=1,vf;
long long sum;
int main()
{
in>>n>>k;
for(int i=1;i<=n;i++)
in>>a[i];
for(int i=1;i<=n;i++)
{
if(coada[last]<=i-k)
last++;
while(last<=vf && a[ coada[vf] ]>=a[i])
vf--;
coada[++vf]=i;
minim[i]=a[ coada[last] ];
}
for(int i=k;i<=n;i++)
sum+=minim[i];
out<<sum;
return 0;
}