记录编号	575112	评测结果	AAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	ZRQ	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-09-03 12:49:09	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005,W=105;
int val[N][W],dp[N][W],ans,w,h,mxt,st[N],top,fr[N][W],cnt;
int main()
{
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout); 
	memset(dp,-1,sizeof(dp));
	scanf("%d%d",&w,&h);
	int stt,pos,v,k;
	while(~scanf("%d%d%d%d",&stt,&pos,&v,&k))
	{
		if((h-1)%v!=0) continue;
		int et=stt+(h-1)/v;
		val[et][pos]+=k;
		mxt=max(mxt,et);
		++cnt;
	}
	dp[0][w/2+1]=val[0][w/2+1];
	if(cnt==1&&val[0][w/2+1])
	{
		printf("%d\n0",val[0][w/2+1]);
		return 0; 
	}
	for(int i=0;i<mxt;++i)
		for(int j=1;j<=w;++j)
		{
			if(dp[i][j]==-1) continue;
			for(int k=2;k>=-2;--k)
			{
				int to=j+k;
				if(to<1||to>w) continue;
				if(dp[i][j]+val[i+1][to]>dp[i+1][to])
				{
					dp[i+1][to]=dp[i][j]+val[i+1][to];
					fr[i+1][to]=k;
				}
			}
		}
	int et,ed,ans=0;
	for(int i=0;i<=mxt;++i)
		for(int j=1;j<=w;++j)
			if(dp[i][j]>ans)
			{
				ans=dp[i][j];
				et=i,ed=j;
			}
	for(int i=et;i>0;--i)
	{
		st[++top]=fr[i][ed];
		ed-=fr[i][ed];
	}
	printf("%d\n",ans);
	for(int i=top;i>=1;--i) printf("%d\n",st[i]);
	return 0;
}