比赛 20110414 评测结果 WAWWWWWWAWWAAWW
题目名称 奶牛的跳格子游戏 最终得分 26
用户昵称 kaaala 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-04-14 09:11:11
显示代码纯文本
#include<fstream>
#include<cmath>
#include<cstdlib>
#include<string>

using namespace std;

long long f[250011],v[250011],sum[250011],p[250011],q[250011],ans=0;
long n,k;

long long mx(long long a,int b)
{
	if(a>b)
		return a;
	else
		return b;
}

int main()
{
	long i,l,r;
	ifstream fin("hop.in");
	ofstream fout("hop.out");
	fin>>n>>k;
	for(i=1;i<=n;i++)
		fin>>v[i];
	memset(sum,0,sizeof(sum));
	for(i=1;i<=n;i++)
		sum[i]=sum[i-1]+mx(v[i],0);
	v[n+1]=0;
	l=1;
	r=1;
	q[1]=0;
	p[1]=0;
	f[0]=0;
	for(i=1;i<=n;i++)
	{
		if(p[1]==0)
			while((l<=r)&&(i-p[1]>=k))
				l++;
		else
			while((l<=r)&&(i-p[1]>k))
				l++;
		f[i]=q[1]+v[i+1]+sum[i-1]+v[i];
		while((l<=r)&&(q[r]<=(f[i]-sum[i+1])))
			r--;
		r++;
		q[r]=f[i]-sum[i+1];
		p[r]=i;
	}
	for(i=1;i<=n;i++)
		if(f[i]-v[i+1]>ans)
			ans=f[i]+v[i+1];
	fout<<ans;
	fin.close();
	fout.close();
	return 0;
}