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

using namespace std;

const int MAXN=260000;
const long long oo=1000000000000000LL;

struct xds
{
	int l,r;
	long long c;
	xds *cl,*cr;
}T[MAXN*2],*root;

int i,j,k,a[MAXN],x,y,ps,n;
long long f[MAXN],ans,t,sum[MAXN];

void mkt(xds *p,int l,int r)
{
	p->l=l;
	p->r=r;
	p->c=0;
	if (r>l)
	{
		int mid=(l+r)>>1;
		++ps;
		p->cl=T+ps;
		mkt(p->cl,l,mid);
		++ps;
		p->cr=T+ps;
		mkt(p->cr,mid+1,r);
	}
}

void cha(xds *p)
{
	if (p->r<x || p->l>y) return;
	if (p->l>=x && p->r<=y)
	{
		if (p->c>t) 
		{
			t=p->c;
		}
		return;
	}
	cha(p->cl);
	cha(p->cr);
}

void ins(xds *p)
{
	if (p->r<i || p->l>i) return;
	if (p->l==p->r)
	{
		p->c=f[i]+sum[n]-sum[i];
		return;
	}
	ins(p->cl);
	ins(p->cr);
	p->c=max(p->cl->c,p->cr->c);
}

int main()
{
	freopen("hop.in","r",stdin);
	freopen("hop.out","w",stdout);
	scanf("%d%d",&n,&k);
	sum[0]=0;
	if (k==0)
	{
		printf("0\n");
		return 0;
	}
	root=T;
	mkt(root,0,n);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		sum[i]=sum[i-1];
		if (a[i]>0) sum[i]+=a[i];
	}
	if (k==1)
	{
		cout<<max(0,a[1])<<endl;
		return 0;
	}
	ans=0;
	i=0;
	f[0]=0;
	ins(root);
	i=1;
	f[1]=a[1];
	ins(root);
	for (i=2;i<=n;i++)
	{
		x=max(i-k,0);
		y=i-2;
		t=-oo;
		cha(root);
		f[i]=a[i]+a[i-1]+t-(sum[n]-sum[i-2]);
		ins(root);
		if (f[i]>ans) ans=f[i];
	}
	cout<<ans<<endl;
	return 0;
}