记录编号	200163	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]道路游戏	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	1.314 s
提交时间	2015-10-28 06:27:49	内存使用	9.75 MiB

#include<cstdio>
#include<cstring>
int n,m,p,pos,now,limit,coin[1010][1010],f[1010][1010];
int maxl[1010],cost[1010];
int main()
{
	freopen("roadgame.in","r",stdin);
	freopen("roadgame.out","w",stdout);
	memset(f,-0x3f,sizeof(f));
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;++i)
	    for(int j=1;j<=m;++j)
	        scanf("%d",&coin[i][j]);
	for(int i=1;i<=n;++i)
		scanf("%d",&cost[i]),f[0][i]=0;
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=n;++j)
		{
			pos=j-1;
			if(!pos)
			    pos=n;
			limit=0;
			if(i-p>limit)
			    limit=i-p;
			now=0;
			for(int k=i-1;k>=limit;--k)
			{
				now+=coin[pos][k+1];
				if(f[i][j]<now-cost[pos]+maxl[k])
					f[i][j]=now-cost[pos]+maxl[k];
				--pos;
				if(!pos)
				    pos=n;
			}
			if(maxl[i]<f[i][j])
			    maxl[i]=f[i][j];
		}
	}
	printf("%d",maxl[m]);
}