记录编号	60910	评测结果	AAAAAAAAAA
题目名称	鱼儿仪仗队	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.196 s
提交时间	2013-06-01 11:48:09	内存使用	19.39 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
#define F_I "guardb.in"
#define F_O "guardb.out"
using namespace std;
typedef long long ll;
const ll Nx=500000;
ll N,K,X[Nx],f[Nx],S[Nx],Q[Nx],g[Nx],t,h;
ll max(ll i,ll j){
	return i>j?i:j;
}
void init(){
ll i;
	cin>>N>>K;
	for(i=1;i<=N;i++){
		cin>>X[i];
		S[i]=S[i-1]+X[i];
	}
}
void bf(){
ll i,j;
	f[1]=X[1];
	for(i=2;i<=N;i++){
		f[i]=f[i-1];
		for(j=max(i-K+1,1);j<=i;j++){
		ll temp=(j>1?f[j-2]:0)+S[i]-S[j-1];
			f[i]=max(f[i],temp);
		}
	}
	printf("%lld\n",f[N]);
}
ll Fig(ll x){
	return (x>1?g[x-2]:0)-S[x-1];
}
void dp(){
ll i,j;
	h=t=1;
	for(i=1;i<=N;i++){
		while(t>h && Q[h]<=i-K)
			h++;
		while(t>h && Fig(Q[t-1])<=Fig(i) )
			t--;
		Q[t++]=i;
		g[i]=max(g[i-1],Fig(Q[h])+S[i]);
	}
	printf("%lld\n",g[N]);
}
int main(){
freopen(F_I,"r",stdin);
freopen(F_O,"w",stdout);
	init();
	
//	bf();
	dp();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}