Pagini recente » Cod sursa (job #1617533) | Cod sursa (job #539640) | Cod sursa (job #1290785) | Cod sursa (job #903074) | Cod sursa (job #1256116)
#include<cstdio>
#include<vector>
#include<deque>
using namespace std;
deque<long long>D,poz;
long long sum,x;
int i,n,k;
int main(){
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d",&n,&k);
for(i=1;i<=k;i++){
scanf("%lld",&x);
while(D.size()>=1&&x<=D.back()){
D.pop_back();
poz.pop_back();
}
D.push_back(x);
poz.push_back(i);
}
long long sum=0;
sum+=D.front();
//printf("%lld\n",D.front());
for(i=k+1;i<=n;i++){
scanf("%lld",&x);
while(D.size()>=1&&x<=D.back()){
D.pop_back();
poz.pop_back();
}
D.push_back(x);
poz.push_back(i);
while(poz.back()-poz.front()+1>k){
D.pop_front();
poz.pop_front();
}
sum+=D.front();
//printf("%lld\n",D.front());
}
printf("%lld",sum);
return 0;
}