Cod sursa(job #698475)
Utilizator | Andrici Cezar andrici_cezar | Data | 29 februarie 2012 14:19:13 |
---|---|---|---|
Problema | Deque | Scor | 25 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <cstdio>
#include <deque>
using namespace std;
deque <long> deq;
long N, K, s, i, A[5000001];
int main() {
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%ld %ld", &N, &K);
for (i = 1; i <= N; ++i) {
scanf("%ld", &A[i]);
}
for (i = 1; i <= N; ++i) {
while (!deq.empty() && A[i] <= A[deq.back()])
deq.pop_back();
deq.push_back(i);
if (deq.front() == i-K)
deq.pop_front();
if (i >= K)
s += A[deq.front()];
}
printf("%ld\n", s);
return 0;
}