Cod sursa(job #2054753)
| Utilizator | Data | 2 noiembrie 2017 15:29:22 | |
|---|---|---|---|
| Problema | Deque | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.47 kb |
#include <iostream>
using namespace std;
const int N = 5000000;
int v[N], d[N];
int main()
{
int n, k, st = 0, sum = 0, dr = -1;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> v[i];
while(st <= dr && d[st] == i - k) {
++st;
}
while(st <= dr && v[i] <= v[d[dr]]) {
--dr;
}
d[++dr] = i;
if( i >= k - 1) {
sum += v[d[st]];
}
}
cout << sum;
return 0;
}
