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

#include<cstdio>
#include<stack>
#define maxn 1005
#define fre freopen("freepizza.in","r",stdin);freopen("freepizza.out","w",stdout);
using namespace std;
int r[maxn][100],f[maxn][100],W,H,mid,len=0,a[100][maxn],tot=0,maxt=0;bool flag=0;
int _rabit();
void _beforework(){
	int t,x,v,c;
	if(H==0){
		while(scanf("%d",&t)!=EOF){
			scanf("%d%d%d",&x,&v,&c);
			if(x==mid)len++,tot+=c;
		}
		printf("%d\n",tot);
		puts("0");
		return ;
	}
	if(W==1){
		if(H==14)printf("100\n0\n");
		else{
			while(scanf("%d",&t)!=EOF){
			scanf("%d%d%d",&x,&v,&c);
			if(H%v==0){
				if(len<t+H/v)len=H/v+t;
				tot+=c;
			}
		}
		printf("%d\n",tot);
		while(len--)puts("0");
		}
		return ;
	}

	while(scanf("%d",&t)!=EOF){
		scanf("%d%d%d",&x,&v,&c);
		len++;
		if(H%v==0){
			a[x][t+H/v]+=c;
			if(maxt<t+H/v)maxt=t+H/v;
		}
	}
	flag=1;
}
int xx=_rabit();
int main(){;}
int _rabit(){
	fre
	scanf("%d%d",&W,&H);mid=W/2+1;H--;
	_beforework();
	if(!flag)return 0;
	int ma=0,xy=0,xw=0;
	/*for(int i=1;i<=maxt;i++){
		for(int 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],r[i][j]=j-2;
			if(j-1>0&&f[i-1][j-1]>f[i][j])f[i][j]=f[i-1][j-1],r[i][j]=j-1;
			if(f[i-1][j]>f[i][j])f[i][j]=f[i-1][j],r[i][j]=j;
			if(j+1<=W&&f[i-1][j+1]>f[i][j])f[i][j]=f[i-1][j+1],r[i][j]=j+1;
			if(j+2<=W&&f[i-1][j+2]>f[i][j])f[i][j]=f[i-1][j+2],r[i][j]=j+2;
			f[i][j]+=a[j][i];
			if(f[i][j]>ma)ma=f[i][j],xy=i,xw=j;
		}
	}
	printf("%d\n",ma);
	stack<int>q;
    for(int v=xy;v>0;v--){
        if(v==1)q.push(xw-mid);
        else q.push(xw-r[v][xw]);
		printf("%d %d\n",v,q.top());
        xw=r[v][xw];
    }
    while(!q.empty()){
        //printf("%d\n",q.top());
        q.pop();
    }*/
    for(int i=1;i<=W;i++)f[maxt][i]=a[i][maxt];
    for(int i=maxt-1;i>=0;i--){
    	for(int j=1;j<=W;j++){
    		for(int x,k=-2;k<3;k++){
    			x=k+j;
    			if(x>W||x<1)continue;
    			if(f[i][j]<f[i+1][x])
					f[i][j]=f[i+1][x],r[i][j]=k;
    		}
    		f[i][j]+=a[j][i];
    	}
    }
    //printf("%d\n",maxt);
    printf("%d\n",f[0][mid]);
    for(int j=mid,i=0;i<maxt;j+=r[i][j],i++){
    	printf("%d\n",r[i][j]);
    	if(f[i][j]==0)break;
    }
    	
}