记录

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6;

int n,k,a[N];
int add[N],f[N],q[N]; 
deque<int> dq;
/*f_i 表示以i结尾时， 1~i的最大价值
	q_i 表示 1~i中最大的 f_i*/
signed main() {
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) add[i]=add[i-1]+a[i];

	int ans=0;
	dq.push_back(0);
	for(int i=1;i<=n;i++) {
		f[i]=max(f[i],q[dq.front()-1]-add[dq.front()]+add[i]);
		q[i]=max(f[i],q[i-1]);
		ans=max(ans,f[i]);
		int x=q[i-1]-add[i];
		while(!dq.empty()&&q[dq.front()-1]-add[dq.front()]<=x) dq.pop_front();
		dq.push_back(i);
		while(!dq.empty()&&dq.front()+k<=i) dq.pop_front();
	}
	cout<<ans;
	return 0;
}