记录编号	58808	评测结果	AAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2013-04-26 20:57:42	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<deque>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int SIZEN=1001,SIZEW=101,SIZET=1001;
class PIE{
public:
	int t,l,v,c;
	//下落时刻,水平位置,下落速度,分值
	PIE(){t=l=v=c=0;}
}p[SIZEN];
int w,h,maxt,n;//舞台宽度,高度
int value[SIZET][SIZEW]={0};//value[i][j]表示i秒钟,j处接到的馅饼分值和
int f[SIZET][SIZEW]={0};
int father[SIZET][SIZEW]={0};//每个状态由何而来
void read(void){
	n=maxt=0;
	scanf("%d%d",&w,&h);
	int t,l,v,c;
	int dt;
	while(scanf("%d%d%d%d",&t,&l,&v,&c)!=EOF){
		//在t时刻,从高处h处下落速度v,水平坐标l,分值c
		if((h-1)%v==0||t==0){
			dt=t+(h-1)/v;
			if(dt>maxt) maxt=dt;
			value[dt][l]+=c;
		}
	}
	/*for(int km=0;km<=maxt;km++){
		for(int lm=1;lm<=w;lm++) cout<<value[km][lm]<<" ";
		cout<<endl;
	}
	cout<<endl;*/
	int i,j;
	for(i=0;i<=maxt;i++){
		for(j=1;j<=w;j++) f[i][j]=-0x7fffffff;
	}
	f[0][(w+1)/2]=value[0][(w+1)/2];
}
void DP(void){
	int i,j;
	for(i=1;i<=maxt;i++){
		for(j=1;j<=w;j++){
			if(j-2>0&&f[i-1][j-2]>f[i][j]){
				f[i][j]=f[i-1][j-2];
				father[i][j]=2;
			}
			if(j-1>0&&f[i-1][j-1]>f[i][j]){
				f[i][j]=f[i-1][j-1];
				father[i][j]=1;
			}
			if(f[i-1][j]>f[i][j]){
				f[i][j]=f[i-1][j];
				father[i][j]=0;
			}
			if(j+1<=w&&f[i-1][j+1]>f[i][j]){
				f[i][j]=f[i-1][j+1];
				father[i][j]=-1;
			}
			if(j+2<=w&&f[i-1][j+2]>f[i][j]){
				f[i][j]=f[i-1][j+2];
				father[i][j]=-2;
			}
			f[i][j]+=value[i][j];
		}
	}
	/*for(int km=0;km<=maxt;km++){
		for(int lm=1;lm<=w;lm++) cout<<f[km][lm]<<" ";
		cout<<endl;
	}
	cout<<endl;
	for(int km=0;km<=maxt;km++){
		for(int lm=1;lm<=w;lm++) cout<<father[km][lm]<<" ";
		cout<<endl;
	}
	cout<<endl;*/
}
void write(void){
	deque<int> ans;
	int final=0;
	int i;
	for(i=1;i<=w;i++){
		if(f[maxt][i]>f[maxt][final]) final=i; 
	}
	bool flag=false;
	int now=final;
	if(maxt==0){
		cout<<f[0][final]<<endl;
		if(f[0][final]) cout<<0<<endl;
		return;
	}
	for(i=maxt;i>=1;i--){
		if(flag){
			ans.push_front(father[i][now]);
			now-=father[i][now];
		}
		else{
			if(value[i][now]||i==1){
				flag=true;
				ans.push_front(father[i][now]);
			}
			now-=father[i][now];
		}
	}
	cout<<f[maxt][final]<<endl;
	for(i=0;i<ans.size();i++){
		cout<<ans[i]<<endl;
	}
}
int main(){
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
	read();
	DP();
	write();
	return 0;
}