#include #include #include #include #include using namespace std; typedef long long int lint; int min(int a, int b) { if (a < b) return a; else return b; } struct Solution { lint total; int rightMostBulb; }; class Solver { public: Solver(int _n, int _k) : n(_n) , k(_k) , c(_n) , sol(_n) { } void read() { for (int i = 0; i < n; ++i) cin >> c[i]; } void solve() { initSol(); for (int i = 1; i < n; ++i) step(i); cout << sol[n-1].total << endl; } private: void initSol() { cerr << "initSol " << c.size() << endl; lint val = c[0]; int index = 0; for (int i = 1; i <= min(k,n); ++i) { cerr << i << endl; if (val > c[i]) { val = c[i]; index = i; } } sol[0].total = val; sol[0].rightMostBulb = index; } lint getCost(int i) { if (i < 0) return 0; else return sol[i].total; } void step(int m) { cerr << "step " << m << endl; int lastBulb = min(m + k, n-1); lint val = c[lastBulb]; int index = lastBulb; lastBulb--; for (; lastBulb >= m - k; --lastBulb) { if (lastBulb < 0) break; if (val > c[lastBulb] + getCost(lastBulb - k - 1)) { val = c[lastBulb] + getCost(lastBulb - k - 1); index = lastBulb; } } sol[m].total = val; sol[m].rightMostBulb = index; } int n; int k; vector c; vector sol; }; int main() { int n, k; cin >> n >> k; Solver s(n, k); s.read(); s.solve(); return 0; }