记录编号	392493	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]金明的预算方案	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2017-04-07 21:19:27	内存使用	1.84 MiB

#include<iostream>
#include<cstdio>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
typedef long long LL;
LL V,n,x,y,z,w[70],v[70],f[200100],v1[70],v2[70],w1[70],w2[70];
int main()
{
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	scanf("%lld%lld",&V,&n);
	V/=10;
	for(LL i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		x/=10;
		if(!z)
		{
			w[i]=x;
		    v[i]=x*y;
		}
		else
		{
			if(w1[z]==0)
			{
				w1[z]=x;
				v1[z]=x*y;
			}
			else
			{
				w2[z]=x;
				v2[z]=x*y;
			}
		}
	}
	for(LL i=1;i<=n;i++)
	 for(LL j=V;j>=w[i];j--)
	 {
	 	    f[j]=max(f[j],f[j-w[i]]+v[i]);
	 		if(w[i]+w1[i]<=j) f[j]=max(f[j],f[j-w[i]-w1[i]]+v[i]+v1[i]);
	 		if(w[i]+w2[i]<=j) f[j]=max(f[j],f[j-w[i]-w2[i]]+v[i]+v2[i]);
	 		if(w[i]+w1[i]+w2[i]<=j) f[j]=max(f[j],f[j-w[i]-w1[i]-w2[i]]+v[i]+v1[i]+v2[i]);
		 
	 }
	printf("%lld",f[V]*10);
	return 0;
}