Pagini recente » Cod sursa (job #825348) | Cod sursa (job #1037381) | Cod sursa (job #2866778) | Cod sursa (job #1199836) | Cod sursa (job #2349748)
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
deque <long long> d1,d2;
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
long long n,i,k,nr,s;
cin>>n>>k;
for(i=1;i<=k;i++)
{
cin>>nr;
while(!d1.empty() && d1.back()>nr)
{
d1.pop_back();
d2.pop_back();
}
d1.push_back(nr);
d2.push_back(i);
}
s=d1.front();
for(i=k+1;i<=n;i++)
{
cin>>nr;
while(!d1.empty() && d1.back()>nr){
d1.pop_back();
d2.pop_back();
}
d1.push_back(nr);
d2.push_back(i);
while(!d1.empty() && d2.front()<i-k+1)
{
d1.pop_front();
d2.pop_front();
}
s=s+d1.front();
}
cout<<s;
return 0;
}