状态表示
f[i] 从前i头牛中选 且合法的所有方案
属性:
总和最大

状态转移
第i头牛与 前i-1头牛分开来看
1 不选第i头牛 = f[i-1](和前i-1头牛的最大值相同)
2 选第i头牛 
对于[i-k,i]继续划分子集 由于不能有连续k个连续编号的牛
所以w[i-k+1] ~ w[i]这k个不能连续,中间要空缺,则对比不选取哪一个w[i-j]使得总和最大
子集 = 空缺w[m] for m in [i-k,i] 

不选w[i-j]则前面的w[1]~w[i-j]这一块的最大值就 = f[i-j-1](从前i-j头牛中选,不选第i-j头牛的最大值)
f[i] = max(f[i-j-1] + s[i] - s[i-j]) for j in range(i-k,i) 
     = max(f[i-j-1] - s[i-j]) +s[i] 
     其中i-j<=k 
     则我们可以维护一个范围为[i-k,k]的队列
     该队列头 维护一个前[i-k,i]中 f[i-j-1]-s[i-j]最大的下标
维护队列流程
    1 如果队列头下标超出区间范围 队列头出队列
    2 用当前区间[i-k,i]中最大f[i-j-1]-s[i-j]+s[i]更新f[i]
    3 由于f[i]已经更新过了 则对于下一个要更新的f[i+1]而言 如果g(i)>g(i-j) 
      则当前下标i对于f[i+1]的价值更大,并且相对于i-j也更接近i+1(更不容易出队列,更安全)
      那么i-j对f[i+1]就没有用了,舍弃i-j,i-j出队列

      直到队列前面有比g(i)大的g(i-j)那就留给下一次循环i+1时判断其是否还在[i+1-k,i+1]这个范围,如果在就依然作为更新f[i+1]的队列头

#include<cstring>
#include<iostream>
#include<algorithm>
#include<deque>
typedef long long LL;
using namespace std;

const int N=100010;
int n,m;
LL s[N],f[N];
int q[N];

LL g(int i)
{
    if(!i) return 0;
    return f[i-1]-s[i];
}

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin >> s[i];
        s[i] += s[i-1];
    }
    deque<int> q;
    q.push_back(0);
    for(int i=1;i<=n;i++)
    {
        if(q.front()<i-m) q.pop_front();
        f[i] = max(f[i-1],g(q.front())+s[i]);
        while(q.size() && g(q.back())<=g(i)) q.pop_back();//对比的是q.back()
        q.push_back(i);
    }
    cout << f[n];
    return 0;
}