比赛 20110414 评测结果 AAAAWAAWAAAWAAA
题目名称 奶牛的跳格子游戏 最终得分 80
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-04-14 11:03:59
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <deque>
#include <iostream>
using namespace std;

typedef long long s64;

const s64 MAXN=250005;
const s64 oo=~0ull>>3;

s64 N,K;
s64 sum[MAXN];
s64 d[MAXN];
s64 w[MAXN];
bool in[MAXN];

int main()
{
	freopen("hop.in","r",stdin);
	freopen("hop.out","w",stdout);
	cin>>N>>K;
	for(s64 i=1;i<=N;i++)
	{
		cin>>w[i];
		if (w[i]>0) sum[i]=sum[i-1]+w[i];
		else sum[i]=sum[i-1];
	}
	if (K==1 || N==1)
	{
		if (w[1]>0) cout<<w[1]<<endl;
		else cout<<0<<endl;
		return 0;
	}
	for(s64 i=0;i<=N;i++)
		d[i]=-oo;
	s64 re=0;
	for(s64 i=2;i<=K;i++)
		d[i]=w[i]+w[i-1]+sum[i-2];
	if (sum[K-1]>0)
		d[K+1]=w[K+1]+w[K]+sum[K-1];
	else
	{
		d[K+1]=-oo;
		for(s64 i=1;i<=K+1-2;i++)
			if (w[i]>d[K+1])
				d[K+1]=w[i];
		d[K+1]+=w[K+1]+w[K];
	}
	deque<pair<s64,s64> >q;
	q.push_back(make_pair(d[2]-sum[2],2));
	in[2]=true;
	for(s64 i=3;i<=N;i++)
	{
		s64 l=max(s64(2),i-K);
		while(q.size() && q.front().second<l)
			q.pop_front();
		if (i-2>=l && !in[i-2])
		{
			in[i-2]=true;
			s64 j=i-2;
			s64 nd=d[j]-sum[j];
			while(q.size() && q.back().first<nd)
				q.pop_back();
			q.push_back(make_pair(nd,i-2));
		}
		s64 nd=q.front().first+w[i]+w[i-1]+sum[i-2];
		if (nd>d[i])
			d[i]=nd;
		/*
		for(s64 j=max(2,i-K);j<=i-2;j++)
		{
			s64 nd=d[j]+sum[i-2]-sum[j]+w[i]+w[i-1];
			if (nd>d[i])
				d[i]=nd;
		}*/
	}
	for(s64 i=2;i<=N;i++)
		if (d[i]+sum[min(i-1+K,N)]-sum[i]>re)
			re=d[i]+sum[min(i-1+K,N)]-sum[i];		
	cout<<re<<endl;
	return 0;
}