记录编号	377455	评测结果	AAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2017-03-01 16:05:32	内存使用	2.72 MiB

#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
#define T 2005
#define N 105
using namespace std;
int w,h,a[T][N],f[T][N],t,maxn,g[T][N],kk;
int max(int a,int b,int c,int d,int e)
{
    if(a>=b&&a>=c&&a>=d&&a>=e) { kk=-2; return a;}
    if(b>=a&&b>=e&&b>=c&&b>=d) { kk=-1; return b;}
    if(c>=e&&c>=d&&c>=a&&c>=b) {kk=0; return c;}
    if(d>=e&&d>=a&&d>=b&&d>=c) { kk=1; return d;}
    kk=2;
    return e;
}
stack<int> q;
int main()
{
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
	memset(f,-0x3f,sizeof(f));
    int aa,bb,cc,dd;
    scanf("%d%d",&w,&h);
    while(scanf("%d%d%d%d",&aa,&bb,&cc,&dd)==4){
      if((h-1)%cc!=0) continue;
      a[aa+(h-1)/cc][bb]+=dd;
      if(aa+(h-1)/cc>t) t=aa+(h-1)/cc;
    }
    f[0][w/2+1]=a[0][w/2+1];
    for(int i=(w/2)-1;i<=(w/2)+3;i++)
    {
      if(i<=0) continue;
      f[1][i]=a[1][i];
    }
    for(int i=2;i<=t;i++)
      for(int j=1;j<=w;j++)
      {
        if(j==1){
          f[i][j]=max(f[i-1][j-1],f[i-1][j-1],f[i-1][j],f[i-1][j+1],f[i-1][j+2])+a[i][j];
          if(kk==-2) kk=-1;
          g[i][j]=j+kk;
        }
        else{
          f[i][j]=max(f[i-1][j-2],f[i-1][j-1],f[i-1][j],f[i-1][j+1],f[i-1][j+2])+a[i][j];
          g[i][j]=j+kk;
        }
      }
    /*for(int i=1;i<=t;i++)
    {
      for(int j=1;j<=w;j++)
        cout<<f[i][j]<<" ";
      cout<<endl;
    }*/
    int nn=t,mm;
    for(int i=1;i<=w;i++)
      if(f[t][i]>maxn) { maxn=f[t][i]; mm=i; }
    cout<<maxn<<endl;
    while(nn)
    {
      q.push(mm);
      mm=g[nn--][mm];
    }
    q.push(w/2+1);
    if(maxn!=0&&q.size()==1)
      cout<<0;
    while(!q.empty())
    {
      int k=q.top();
      q.pop();
      if(!q.empty())
        cout<<q.top()-k<<endl;
    }
    //while(1);
    return 0;
}