Cod sursa(job #508266)
#include <stdio.h>
#include <deque>
using namespace std;
deque<pair<int,int> > A;
deque<pair<int,int> >::reverse_iterator it;
int i,d,n,x;
long long smin;
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d",&n,&d);
for(i=1;i<=d;i++)
{
scanf("%d",&x);
it=A.rbegin();
while(it!=A.rend()&&it->first>x)
{
A.pop_back();
it=A.rbegin();
}
A.push_back(make_pair(x,i));
}
smin=A.front().first;
for(i=d+1;i<=n;i++)
{
scanf("%d",&x);
it=A.rbegin();
while(it!=A.rend()&&it->first>x)
{
A.pop_back();
it=A.rbegin();
}
A.push_back(make_pair(x,i));
if(i-A.front().second>=d) A.pop_front();
smin+=A.front().first;
}
printf("%lld\n",smin);
return 0;
}