Pagini recente » Cod sursa (job #521689) | Clasament concurs_infoarena | Cod sursa (job #411540) | Cod sursa (job #2800) | Cod sursa (job #1758868)
#include <cstdio>
#include <deque>
using namespace std;
deque<pair <int, int> >d;
pair<int, int>aux;
int main(){
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int n, k;
long long s = 0;
scanf("%d%d", &n, &k);
for (aux.second = 1; aux.second <= k; ++ aux.second){
scanf("%d", &aux.first);
while (!d.empty() && d.back().first >= aux.first)
d.pop_back();
d.push_back(aux);
}
s = d.front().first;
for (aux.second = k + 1; aux.second <= n; ++ aux.second){
scanf("%d", &aux.first);
while (!d.empty() && d.back().first >= aux.first)
d.pop_back();
d.push_back(aux);
if (d.front().second == aux.second - k)
d.pop_front();
s += d.front().first;
}
printf("%lld\n", s);
return 0;
}