Pagini recente » Cod sursa (job #1989436) | Cod sursa (job #1118608) | Cod sursa (job #1721959) | Cod sursa (job #3146511) | Cod sursa (job #2546447)
#include <bits/stdc++.h>
using namespace std;
int v[100005];
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int n,i,k;
deque<int>deq;
deque<int>poz;
int sum=0;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
{scanf("%d",&v[i]);
if(deq.empty())
{
deq.push_back(v[i]);
poz.push_back(i);
continue;
}
if(i<=k)
{
while(!deq.empty()&&deq.back()>v[i])
{
deq.pop_back();
poz.pop_back();
}
deq.push_back(v[i]);
poz.push_back(i);
if(i==k)
{
sum+=deq.front();
}
}
else
{
while(!deq.empty()&&deq.back()>v[i])
{
deq.pop_back();
poz.pop_back();
}
deq.push_back(v[i]);
poz.push_back(i);
if(poz.front()==(i-k))poz.pop_front(),deq.pop_front();
sum+=deq.front();
}
}
cout<<sum;
return 0;
}