Pagini recente » Cod sursa (job #2091086) | Cod sursa (job #335634) | Cod sursa (job #920886) | Cod sursa (job #254651) | Cod sursa (job #2502282)
#include <cstdio>
#include <deque>
using namespace std;
long long n,k,nr,suma;
deque < pair <int,long long> > chestie;
int main () {
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%lld%lld", &n, &k);
for(int i=1;i<k;++i) {
scanf("%lld", &nr);
if(chestie.empty())
chestie.push_back(make_pair(i,nr));
else {
while(!chestie.empty() && chestie.back().second>=nr)
chestie.pop_back();
chestie.push_back(make_pair(i,nr));
}
}
//suma+=chestie.front().second;
for(int i=k;i<=n;++i) {
scanf("%lld", &nr);
if(chestie.empty())
chestie.push_back(make_pair(i,nr));
else {
while(!chestie.empty() && chestie.back().second>=nr)
chestie.pop_back();
chestie.push_back(make_pair(i,nr));
}
if(i-chestie.front().first>=k)
chestie.pop_front();
suma=suma+chestie.front().second;
}
printf("%lld", suma);
return 0;
}