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

using namespace std;

const int maxn=255555;
const long long oo=555555555555555LL;
int w[maxn],n,k;
long long f[maxn];
long long sum[maxn];

void init()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",w+i);
		sum[i]=sum[i-1] + (w[i]>0 ? w[i] : 0);
	}
}

struct queue
{
	long long x[maxn];
	int id[maxn];
	int qt,qw;
	
	void reset()
	{
		qw=-1,qt=0;
	}
	
	void add(int idx,long long v)
	{
		while (qt<=qw && v>x[qw]) --qw;
		id[++qw]=idx;
		x[qw]=v;
	}
	
	int getj(int lim)
	{
		while (id[qt]<lim) ++qt;
		return id[qt];
	}
}Q;

void solve()
{
	long long ans=0;
	f[1]=w[1];
	ans=max(ans,f[1]);
	if (k==1)
	{	
		printf("%lld\n",ans);
		return ;
	}
	Q.reset();
	for (int i=2;i<=n;i++)
	{
		Q.add(i-2,f[i-2]-sum[i-2]);
		int j=Q.getj(i-k);
		f[i]=sum[i-2]+w[i]+w[i-1]+f[j]-sum[j];
		ans=max(ans,f[i]);
		if (k>2)
		{
			j=Q.getj(i-k+1);
			ans=max(ans,sum[i-1]+w[i]+f[j]-sum[j]);
		}
	}
	printf("%lld\n",ans);
}

int main()
{
	freopen("hop.in","r",stdin);
	freopen("hop.out","w",stdout);
	init();
	solve();
	return 0;
}