Pagini recente » Cod sursa (job #3199645) | Cod sursa (job #1581695) | Cod sursa (job #1547196) | Cod sursa (job #402324) | Cod sursa (job #1647943)
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
deque< pair<int,int> > dq;
int n,k,num;
long long sol;
int main()
{
int i,j;
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d",&n,&k);
scanf("%d",&num);
dq.push_back( make_pair(num,1) );
for(i=2;i<k;i++)
{
scanf("%d",&num);
while(!dq.empty() && dq.back().first>num ) dq.pop_back();
dq.push_back( make_pair(num,i) );
}
for(i=k;i<=n;i++)
{
scanf("%d",&num);
if(i-dq.front().second>=k) dq.pop_front();
while(!dq.empty() && dq.back().first>num) dq.pop_back();
dq.push_back( make_pair(num,i) );
sol+=dq.front().first;
}
printf("%d\n",sol);
fclose(stdin);
fclose(stdout);
return 0;
}