记录编号	49526	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	还是“金明的预算方案”	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2012-11-08 13:18:13	内存使用	3.96 MiB

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <queue>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;
int a[60][3],b,c,d,l,m,n=1,r[3201],k[3201],i[3201],p[1000000],q[2000],x,y,z,j,s;
int main(void)
{
    freopen("budgetb.in","r",stdin);
    freopen("budgetb.out","w",stdout);
	scanf("%d%d%d",&b,&c,&d);
	b/=10;
	for (l=1;l<=c;l++)
	{
		scanf("%d%d%d",&a[l][0],&a[l][1],&a[l][2]);
		a[l][0]/=10;
	}
	for (l=1;l<=c;l++)
		if (a[l][2]==0)
		{
			memset(k,0,sizeof(k));
			memset(q,0,sizeof(q));
			memset(i,0,sizeof(i));
			k[a[l][0]]=a[l][0]*a[l][1];
			q[0]=a[l][0];
			z=1;
			for (m=1;m<=c;m++)
				if (a[m][2]==l)
				{
					y=z;
					for (j=0;j<y;j++)
						if (q[j]+a[m][0]<=b&&k[q[j]+a[m][0]]<k[q[j]]+a[m][0]*a[m][1])
						{
							if (k[q[j]+a[m][0]]==0)
							{
								q[z]=q[j]+a[m][0];
								z++;
							}
							k[q[j]+a[m][0]]=k[q[j]]+a[m][0]*a[m][1];
						}
				}
			y=n;
			for (m=0;m<=b;m++) i[m]=r[m];
			for (m=0;m<z;m++)
			{
				for (j=0;j<y;j++)
					if (p[j]+q[m]<=b&&i[p[j]+q[m]]<r[p[j]]+k[q[m]])
					{
						if (i[p[j]+q[m]]==0)
						{
							p[n]=p[j]+q[m];
							n++;
						}
						i[p[j]+q[m]]=r[p[j]]+k[q[m]];
					}
			}
			for (m=0;m<=b;m++) r[m]=i[m];
		}
	for (l=b;l>=0;l--)
		if (r[l]>s) s=r[l];
	s*=10;
	printf("%d",s);
	fclose(stdin);
    fclose(stdout);
    return 0;
}