Pagini recente » Cod sursa (job #353033) | Cod sursa (job #894219) | Cod sursa (job #1716218) | Cod sursa (job #1850631) | Cod sursa (job #754689)
Cod sursa(job #754689)
#include<cstdio>
#include<deque>
using namespace std;
deque<int> d;
long long v[5000005];
void putnr(int x)
{
while(d.size()&&v[d.back()]>v[x])
d.pop_back();
d.push_back (x);
}
int main()
{
freopen ("deque.in","r",stdin);
freopen ("deque.out","w",stdout);
int n,k;
scanf ("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf ("%lld",v+i);
for(int i=0;i<k;i++)
putnr (i);
long long s=v[d.front()];
for(int i=k;i<n;i++){
putnr (i);
while(d.front()<=i-k)
d.pop_front();
s+=v[d.front()];
}
printf ("%lld",s);
return 0;
}