记录编号	559027	评测结果	AAAAAAAAAA
题目名称	最大子序和	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.072 s
提交时间	2021-02-09 17:36:32	内存使用	3.08 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 300005;
int q[maxn],head = 1,tail = 0,n,m;
long long a[maxn],sum[maxn];
int main() {
	freopen("maxsubseqsum.in","r",stdin);
	freopen("maxsubseqsum.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++ i) {
		scanf("%lld",&a[i]);
		sum[i] = sum[i - 1] + a[i];
	}
	long long ans = a[1];
	q[++ tail] = 0;
	for(int i = 2;i <= n;++ i) {
		while(head <= tail&&i - q[head] > m)++ head;
		ans = max(ans , sum[i] - sum[q[head]]);
		while(head <= tail&&sum[q[tail]] > sum[i - 1])-- tail;
		q[++ tail] = i - 1;         
	}
	printf("%lld",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}