记录编号	575258	评测结果	AAAAAA
题目名称	[NOI 1998]免费馅饼	最终得分	100
用户昵称	00000	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-09-08 17:07:27	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int wi,h;
int t[3000],p[3000],v[3000],s[3000];
int n=1;
int f[3000][3000],r[3000][3000];//f时间，位置  r路径 
int l;//记录最后时间 
int k[20]={0,-2,-1,0,1,2};
void dp(int x,int y)//f(x,y)
{
	int ans=-1,rr=-2;
	for(int q=1;q<=5;q++)
	{
		if(y+k[q]>=1&&f[x+1][y+k[q]]>ans&&y+k[q]<=wi)
		{
			rr=k[q];
			ans=f[x+1][y+k[q]];
		}
	}
	f[x][y]+=ans;
	r[x][y]=rr;
} 
int main(){
	freopen("freepizza.in","r",stdin);
	freopen("freepizza.out","w",stdout);
cin>>wi>>h;
while(cin>>t[n]>>p[n]>>v[n]>>s[n]) n++;
n--;
for(int q=1;q<=n;q++)
{
	if((h-1)%v[q]==0) 
	{
		l=max(l,t[q]+(h-1)/v[q]);
		f[t[q]+(h-1)/v[q]][p[q]]+=s[q];
	}
}
for(int q=l;q>=0;q--)
	for(int w=1;w<=wi;w++)
		dp(q,w);
int now=(wi+1)/2;
cout<<f[0][now]<<endl;
if(n==0) return 0;
int d=0;
for(int q=0;q<=l;q++)
{
	if(f[q+1][now+r[q][now]]!=f[q][now]) d=q;
	now+=r[q][now];
}
d--;now=(wi+1)/2;
d=max(d,0);
for(int q=0;q<=d;q++)
{
	cout<<r[q][now]<<endl;
	now+=r[q][now];
}
return 0;
}