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

#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll SIZEN=100001;
class PAIR{
public:
	ll ind;//下标
	ll data;//数据
};
class MONO_QUEUE_MAX{
public:
	deque<PAIR> s;
	MONO_QUEUE_MAX(){s.clear();}
	void insert(PAIR x){
		while(!s.empty()&&x.data>=s.back().data) s.pop_back();
		s.push_back(x);
	}
	void erase(ll x){//删除下标为x的元素
		if(x<0) return;
		if(!s.empty()&&s.front().ind==x) s.pop_front();
		//否则前面删过了
	}
	PAIR maxima(void){
		return s.front();
	}
};
MONO_QUEUE_MAX Q;
ll f[SIZEN]={0};
ll x[SIZEN]={0};
ll s[SIZEN]={0};
ll n,k;
//下标从1开始
void read(void){
	scanf("%lld%lld",&n,&k);
	ll i;
	for(i=1;i<=n;i++) scanf("%lld",&s[i]),s[i]+=s[i-1];
}
void work(void){
	ll i;
	Q.insert((PAIR){0,0});
	PAIR temp;
	for(i=1;i<=n;i++){
		Q.erase(i-k-2);
		temp=Q.maxima();
		f[i]=max(f[i],f[temp.ind]+s[i-1]-s[temp.ind]);
		Q.insert((PAIR){i,f[i]-s[i]});
	}
}
void write(void){
	long long ans=0,i;
	for(i=n;i>=n-k&&i>=0;i--){
		if(f[i]+s[n]-s[i]>ans){
			ans=f[i]+s[n]-s[i];
		}
	}
	cout<<ans<<endl;
}
int main(){
	freopen("guardb.in","r",stdin);
	freopen("guardb.out","w",stdout);
	read();
	work();
	write();
	return 0;
}