记录编号	163962	评测结果	AAAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-05-27 12:21:55	内存使用	2.18 MiB

#include<cstdio>

using namespace std;

int w,h,f[1500][110],a[1500][110],pre[1500][110];

void out(int i,int j)
{
	if(i==0)
	{
		if(pre[i][j]!=3)
		    printf("%d\n",pre[i][j]);
		return;
	}
	out(i-1,j-pre[i][j]);
	printf("%d\n",pre[i][j]);
}

int main()
{
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
	scanf("%d%d",&w,&h);
	int t,pos,v,val;
	int maxt=0;
	while(scanf("%d%d%d%d",&t,&pos,&v,&val)==4)
	{
		if((h-1)%v==0||h==1||w==1)
		{
			a[(h-1)/v+t][pos]+=val;
			if((h-1)/v+t>maxt)
			    maxt=(h-1)/v+t;
		}
	}
	for(int i=0;i<=maxt;i++)
	{
		for(int j=0;j<=w;j++)
	    {
			f[i][j]=-0x3fffffff;
			pre[i][j]=3;
	    }
	}
	f[0][w/2+1]=a[0][w/2+1];
	if(f[0][w/2+1]!=0)
		pre[0][w/2+1]=0;
	int lastt=0,lastw=w/2+1,maxv=a[0][w/2+1];
	for(int i=1;i<=maxt;i++)
	{
		for(int j=1;j<=w;j++)
		{
			for(int k=-2;k<=2;k++)
			{
				if(k+j>0&&k+j<=w)
				{
					if(f[i][j]<f[i-1][j+k]+a[i][j])
					{
						f[i][j]=f[i-1][j+k]+a[i][j];
						pre[i][j]=-k;
						if(f[i][j]>maxv)
						{
							maxv=f[i][j];
							lastt=i;
							lastw=j;
						}
					}
				}
			}
		}
	}
	printf("%d\n",maxv);
	out(lastt,lastw);
	return 0;
}