记录编号	252402	评测结果	AAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-20 11:31:42	内存使用	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<=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",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;
    }
}