RT

期望得分100 实际得分20

本来自己写，发现过不了样例，于是推翻并面向题解编程，照着题解调，发现仍然过不了

用的第一页倒数第二篇题解，写了个STL版

#include<bits/stdc++.h>
//#include<iostream>
//#include<algorithm>　　　　　　
//#include<cctype>
//#include<cmath>　　　
//#include<cstdio>
//#include<cstdlib>
//#include<cstring>
//#include<ctime>　　　　　　
//#include<fstream>　　　
//#include<map>　　　　　　
//#include<iomanip>　　　
//#include<iostream>　　　
//#include<queue>　　　　
//#include<set>　　　　　　
//#include<sstream>　　　　
//#include<stack>　　　　　　　　
//#include<string>　　　　　　
//#include<vector>
using namespace std;
long long n,k;
deque<long long>qwq;
long long qzh[1000005];
long long dp[1000005][2];
long long orz[1000005];
int main(){
	cin>>n>>k;
	for(long long i=1;i<=n;i++){
		cin>>orz[i];
		qzh[i]=qzh[i-1]+orz[i];
	}
	memset(dp,0,sizeof(dp));
	dp[1][1]=orz[1];
	for(long long i=2;i<=n;i++){
		dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
		while(!qwq.empty()&&qwq.back()<i-k)qwq.pop_back();
		if(qwq.empty())dp[i][1]=dp[0][0]-qzh[0]+qzh[i];
		else dp[i][1]=dp[qwq.back()][0]-qzh[qwq.back()]+qzh[i];
		
		while(!qwq.empty()&&qzh[i]-dp[i][0]<qzh[qwq.front()]-dp[qwq.front()][0])qwq.pop_front(); 
		qwq.push_front(i);
	}
	cout<<max(dp[n][0],dp[n][1]);
	return 0;
}

求调QAQ