Pagini recente » Cod sursa (job #1701969) | Cod sursa (job #1716470) | Cod sursa (job #1181435) | Cod sursa (job #43940) | Cod sursa (job #1647940)
#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.back().first>num ) dq.pop_back();
dq.push_back( make_pair(num,i) );
} sol+=dq.front().first;
for(i=k+1;i<=n;i++)
{
scanf("%d",&num);
while(dq.back().first>num) dq.pop_back();
if(dq.size()) if(i-dq.front().second>=k) dq.pop_front();
dq.push_back( make_pair(num,i) );
if(i==n) cout<<dq.front().first;
sol+=dq.front().first;
}
printf("%d\n",sol);
fclose(stdin);
fclose(stdout);
return 0;
}