记录编号	199867	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2009]道路游戏	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.105 s
提交时间	2015-10-27 17:43:07	内存使用	8.11 MiB

#include<cstdio>
#include<deque>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEN=1010,INF=0x7fffffff/2;
int N,M,P;
int f[SIZEN]={0},f1[SIZEN]={0};
int tim[SIZEN][SIZEN]={0};//第j个时可第i号点的机器人还能走多长时间
int fm[SIZEN]={0};
int a[SIZEN][SIZEN]={0};
int cost[SIZEN]={0};
void read()
{
	scanf("%d%d%d",&N,&M,&P);
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) scanf("%d",&a[i][j]);
	for(int i=1;i<=N;i++) scanf("%d",&cost[i]);	
}
void work()
{
	for(int i=1;i<=M;i++) fm[i]=-INF;
	for(int j=1;j<=M;j++)
	{
		memset(f,0,sizeof(f));
		for(int i=1;i<=N;i++)
		{
			int now=i-1;
			if(now==0) now=N;
			if(tim[j-1][now]==0)
			{
				f[i]=fm[j-1]-cost[i]+a[i][j];
				tim[j][i]=P-1;
			}
			else if(fm[j-1]-cost[i]>=f1[now])
			{
				f[i]=fm[j-1]-cost[i]+a[i][j];
				tim[j][i]=P-1;
			}
			else 
			{
				f[i]=f1[now]+a[i][j];
				tim[j][i]=tim[j-1][now]-1;
			}
			if(f[i]>fm[j]) fm[j]=f[i];
		}
		for(int i=1;i<=N;i++) f1[i]=f[i];
	}
	printf("%d",fm[M]);
}
int main()
{
	freopen("roadgame.in","r",stdin);
	freopen("roadgame.out","w",stdout);
	read();
	work();
	return 0;
}