Pagini recente » Cod sursa (job #1421611) | Cod sursa (job #2349760)
#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;
scanf("%lld %lld",&n, &k);
for(i=1;i<=k;i++)
{
///cin>>nr;
scanf("%lld", &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;
scanf("%lld", &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;
}