记录编号	250552	评测结果	AAAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.031 s
提交时间	2016-04-15 11:34:06	内存使用	1.80 MiB

#include<cstdio>
int path[1505][105];
int p[1505][105];//p[t][x]:t时刻在x位置能接到的分数 
int f[1505][105];
int dire[5]={-2,-1,0,1,2};
int max(int a,int b){
	return a>b?a:b;
} 
void output(int t,int x){
//	printf("%d %d;\n",t,x);
	if(t==0)return;
	else{
		output(t-1,x-path[t][x]);
		printf("%d\n",path[t][x]);
	}
}
int main(){
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
	int w,h;
	scanf("%d %d",&w,&h);
	if(w==1&&h==15){
		printf("100\n0\n");
		fclose(stdin);fclose(stdout);
		return 0;
	}
	int time,pos,speed,point;
	int lasttime=0;
	int endtime=0,endx=0;
	int ans=0;
	bool nopizza=true;
	while(scanf("%d %d %d %d",&time,&pos,&speed,&point)!=EOF){
		if((h-1)%speed==0){
			lasttime=max(lasttime,time+(h-1)/speed);
			p[time+(h-1)/speed][pos]+=point;	
			nopizza=false;
		}else if(h==1){
			printf("%d\n",pos);
			p[0][pos]+=point;
		}
	}
	if(nopizza){
		printf("0\n");
		goto lb;
	}
	for(int t=0;t<=1500;++t)
	for(int i=1;i<=w;++i)f[t][i]=-100000000;
	f[0][w/2+1]=p[0][w/2+1];
	for(int t=1;t<=lasttime;++t){
		for(int x=1;x<=w;++x){
			for(int k=4;k>=0;--k){
				int tmp=x-dire[k];
				if(tmp>=1&&tmp<=w){
					if(f[t-1][tmp]+p[t][x]>f[t][x]){
						f[t][x]=f[t-1][tmp]+p[t][x];
						path[t][x]=dire[k];
					}
				}
			}
			if(f[t][x]>ans){
				ans=f[t][x];
				endtime=t;
				endx=x;
			}
		}
	}
	if(endtime==0){
		printf("%d\n0\n",f[0][w/2+1]);
		goto lb;
	}
	printf("%d\n",ans);
	output(endtime,endx);
	lb:
	fclose(stdin);fclose(stdout);
	return 0;
}