记录编号	163235	评测结果	AAAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-05-23 18:16:34	内存使用	6.57 MiB

#define MAXT 5001LL
#define MAXW 101LL

#include <cstdio>
#include <cstring>

using namespace std;

inline int in(){
	int temp=0;char c=getchar();
	while(c<'0'||c>'9'){
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()){
		temp=temp*10+c-48;
	}
	return temp;
}

int f[MAXT][MAXW],w,h,st,pos,v,score,data[MAXT][MAXW],ans[MAXT][MAXW],temp,maxt,ANS,maxpos,out[MAXT],final_pos;
bool ex[MAXT][MAXW];

int main(){
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
	w=in();h=in();
	while(scanf("%d",&st)==1){
		pos=in();v=in();score=in();
		if((h-1)%v==0||w==1){
			temp=(h-1)/v+st;
			data[temp][pos]+=score;
			if(maxt<temp){
				maxt=temp;
			}
		}
	}
	v=(w>>1)+1;
	f[0][v]=data[0][v];
	ex[0][v]=1;
	for(int i=0;i<=maxt;i++){
		for(int j=1;j<=w;j++){
			if(ex[i][j]){
				int I=i+1;
				if((j>2&&ex[I][j-2]==0)||(j>2&&f[I][j-2]<f[i][j]+data[I][j-2])){
					f[I][j-2]=f[i][j]+data[I][j-2];
					ans[I][j-2]=-2;
					ex[I][j-2]=1;
				}
				if((j>1&&ex[I][j-1]==0)||(j>1&&f[I][j-1]<f[i][j]+data[I][j-1])){
					f[I][j-1]=f[i][j]+data[I][j-1];
					ans[I][j-1]=-1;
					ex[I][j-1]=1;
				}
				if((ex[I][j]==0)||(f[I][j]<f[i][j]+data[I][j])){
					f[I][j]=f[i][j]+data[I][j];
					ans[I][j]=0;
					ex[I][j]=1;
				}
				if((!ex[I][j+1]&&j+1<=w)||(f[I][j+1]<f[i][j]+data[I][j+1]&&j+1<=w)){
					f[I][j+1]=f[i][j]+data[I][j+1];
					ans[I][j+1]=1;
					ex[I][j+1]=1;
				}
				if((!ex[I][j+2]&&j+2<=w)||(f[I][j+2]<f[i][j]+data[I][j+2]&&j+2<=w)){
					f[I][j+2]=f[i][j]+data[I][j+2];
					ans[I][j+2]=2;
					ex[I][j+2]=1;
				}
			}
		}
	}
	for(int i=1;i<=w;i++){
		if(ANS<f[maxt][i]){
			ANS=f[maxt][i];
		}
	}
	printf("%d\n",ANS);
	for(int i=maxt-1;i>=0;i--){
		int max_now=0;
		for(int j=1;j<=w;j++){
			if(max_now<=f[i][j]){
				max_now=f[i][j];
			}
		}
		if(max_now!=ANS){
			pos=i+1;
			break;
		}
	}
	int max_now=0;
	for(int i=1;i<=w;i++){
		if(f[pos][i]>max_now){
			max_now=f[pos][i];
			final_pos=i;
		}
	}
	for(int i=pos;i>=1;i--){
		out[i]=ans[i][final_pos];
		final_pos-=ans[i][final_pos];
	}
	for(int i=1;i<=pos;i++){
		printf("%d\n",out[i]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}