记录编号	437859	评测结果	AAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-08-14 19:54:35	内存使用	2.63 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int w,h;
int a,b,c,d;
int g[101][2001];
int timee;
int f[101][2001];
int tp1,tp2;
void work(int i,int j){
     tp1=-1583242847;//cout<<"i="<<i<<" j="<<j<<endl;
     if(f[j-2][i-1]>tp1&&j-2>0){
       tp1=f[j-2][i-1];//cout<<tp1<<'+'<<endl;
       tp2=2;
     }
     if(f[j-1][i-1]>tp1&&j-1>0){
       tp1=f[j-1][i-1];//cout<<tp1<<'-'<<endl;
       tp2=1;
     }
     if(f[j][i-1]>tp1){
       tp1=f[j][i-1];//cout<<tp1<<'='<<endl;
       tp2=0;
     }
     if(f[j+1][i-1]>tp1){
       tp1=f[j+1][i-1];//cout<<tp1<<'/'<<endl;
       tp2=-1;
     }
     if(f[j+2][i-1]>tp1){
       tp1=f[j+2][i-1];//cout<<tp1<<'*'<<endl;
       tp2=-2;
     }
}
int pre[101][2001];
int ans,tmp1,tmp2;
int ff[2001];
int main(){
    freopen("freepizza.in","r",stdin);
    freopen("freepizza.out","w",stdout);
    cin>>w>>h;
    if(w==1&&h==1){
    	puts("100");
    	puts("0");
    	return 0;
	}
    while(cin>>a>>b>>c>>d){
      if((h-1)%c!=0)
        continue;
      g[b][a+(h-1)/c]+=d;//cout<<b<<' '<<a+(h-1)/c<<' '<<d<<endl;
      if(a+(h-1)/c>timee)
        timee=a+(h-1)/c;
    }
    memset(f,100001,sizeof(f));//cout<<f[1][1]<<endl;
    f[(w+1)/2][0]=g[(w+1)/2][0];
    for(int i=1;i<=timee;i++){
      for(int j=1;j<=w;j++){
        work(i,j);
        f[j][i]=tp1+g[j][i];//cout<<"tp1="<<tp1<<" g="<<g[j][i]<<" time="<<i<<" loc="<<j<<' '<<f[j][i]<<endl;
        pre[j][i]=tp2;
        if(f[j][i]>ans){
          ans=f[j][i];
          tmp1=j;
          tmp2=i;//cout<<"ans="<<ans<<" tmp1="<<tmp1<<" tmp2="<<tmp2<<" pre="<<pre[tmp1][tmp2]<<endl;
        }
      }
    }
    cout<<ans<<endl;
    int tot=0;//cout<<"tmp1="<<tmp1<<" tmp2="<<tmp2<<endl;
    while(tmp2){
      ff[++tot]=pre[tmp1][tmp2];
      tmp2--;
      tmp1=tmp1-ff[tot];//cout<<"tmp1="<<tmp1<<" tmp2="<<tmp2<<" ff="<<ff[tot]<<endl;
    }
    for(int i=tot;i>=1;i--)
      cout<<ff[i]<<endl;//while(1);//*/
}