记录编号	164463	评测结果	AAAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	OI88	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-05-30 19:37:35	内存使用	2.60 MiB

#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
int data[1005][200],f[1005][200],pre[1005][200],ans[1005],MAX,w,h,tot=1,innitial;
bool flag=false,num=false;
int ret;
char ch;
int in()
{
    ret=0;
    while(ch=getchar(),!isdigit(ch));
    while(ret=ret*10+ch-'0',ch=getchar(),isdigit(ch));
    return ret;
}
void work()
{
	memset(f,128,sizeof(f));
	f[0][innitial]=data[0][innitial];
	for(int i=1;i<=MAX;i++)
	{
		for(int j=1;j<=w;j++)
		{
   			for(int k=2;k>=-2;k--)
			{
				if(j-k>0 && j-k<=w && f[i-1][j-k]>f[i][j])
				{
					f[i][j]=f[i-1][j-k];
					pre[i][j]=k;
				}
			}
			f[i][j]+=data[i][j];
		}
	}
	int final=0;
	for(int i=1;i<=w;i++)
		if(f[MAX][i]>f[MAX][final])
			final=i;
	if(MAX==0)
		printf("%d\n",f[0][final]);
	printf("%d\n",f[MAX][final]);
	for(int i=MAX;i;i--)
	{
		if(num==true)
		{
			ans[tot++]=pre[i][final];
			final-=pre[i][final];
		}
		else
		{
			if(data[i][final] || i==1)
			{
				num=true;
				ans[tot++]=pre[i][final];
			}
			final-=pre[i][final];
		}
	}
	for(int i=tot-1;i;i--)
		printf("%d\n",ans[i]);
}
int main()
{
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
	w=in();
	h=in();
	if(w==1 && h==1)
	{
		printf("100\n0");
		return 0;
	}
	innitial=(w+1)>>1;
	int atime,pos,speed,value;
	h--;
	while(scanf("%d%d%d%d",&atime,&pos,&speed,&value)!=EOF)
	{
		flag=true;
		if(h%speed==0||atime==0)
		{
			int n=atime+h/speed;
			if(n>MAX)
				MAX=n;
			data[n][pos]+=value;
		}
	}
	if(flag==false)
		printf("0");
	else
		work();
}