Pagini recente » Cod sursa (job #92439) | Cod sursa (job #1662997) | Cod sursa (job #2718080) | Cod sursa (job #1928477) | Cod sursa (job #307896)
Cod sursa(job #307896)
#include<stdio.h>
#include<deque>
#include<utility>
using namespace std;
int n,k,i,v;
long long sol;
void readd(),solve(),printt();
deque< pair<int,int> > Q;
int main()
{
readd();
solve();
return 0;
}
void readd()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d",&n,&k);
}
void solve()
{
pair<int,int> x;
for(i=1;i<k;i++)
{
scanf("%d",&v);
while(!Q.empty()&&v<Q.back().first)Q.pop_back();
x.first=v;x.second=i;
Q.push_back(x);
}
for(i=k;i<=n;i++)
{
scanf("%d",&v);
while(!Q.empty()&&v<Q.back().first)Q.pop_back();
x.first=v;x.second=i;
Q.push_back(x);
if(Q.back().second-Q.front().second==k)
Q.pop_front();
sol+=Q.front().first;
}
printf("%lld\n",sol);
}