1 #include <cstdio> 2  3 const int MAXN = 1000001; 4 int n, m, h = 1, t = 1, ans = ~(1 << 31); 5 int q[MAXN], a[MAXN], f[MAXN]; 6  7 inline int min(int x, int y) 8 { 9     return x < y ? x : y;10 }11 12 int main()13 {14     int i;15     scanf("%d %d", &n, &m);16     for(i = 1; i <= n; i++) scanf("%d", &a[i]);17     for(i = 1; i <= n; i++)18     {19         while(h <= t && q[h] < i - m) h++;20         f[i] = f[q[h]] + a[i];21         while(h <= t && f[q[t]] > f[i]) t--;22         q[++t] = i;23      }24      for(i = n - m + 1; i <= n; i++) ans = min(ans, f[i]);25      printf("%d\n", ans);26      return 0;27 }