Pagini recente » Cod sursa (job #1061361) | Cod sursa (job #3230026) | Cod sursa (job #328460) | Cod sursa (job #155810) | Cod sursa (job #715710)
Cod sursa(job #715710)
#include <cstdio>
#include <deque>
#define nMax 5000010
using namespace std;
deque <int> deq;
int a[nMax];
long long s;
int k;
int n;
void adauga(int x)
{
while (!deq.empty() && a[deq.front()] > a[x]){
deq.pop_front();
}
if (!deq.empty() && deq.back() + k <= x){
deq.pop_back();
}
deq.push_front(x);
// s += a[deq.back()];
}
void citire()
{
scanf ("%d %d", &n, &k);
for (int i = 0; i < k; ++ i){
scanf ("%d", &a[i]);
adauga(i);
}
s += a[deq.back()];
for (int i = k; i < n; ++ i){
scanf ("%d", &a[i]);
adauga(i);
s += a[deq.back()];
}
}
int main()
{
freopen ("deque.in", "r", stdin);
freopen ("deque.out", "w", stdout);
citire();
printf ("%lld\n", s);
return 0;
}