Pagini recente » Cod sursa (job #620681) | Cod sursa (job #1669425) | Cod sursa (job #3277737) | Cod sursa (job #1922888) | Cod sursa (job #715700)
Cod sursa(job #715700)
#include <cstdio>
#include <deque>
#define nMax 5000010
using namespace std;
deque <int> deq;
int a[nMax];
int s;
int k;
int n;
void adauga(int x)
{
while (!deq.empty() && a[deq.front()] >= a[x]){
deq.pop_front();
}
while (!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 ("%d\n", s);
return 0;
}