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

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<deque>
#define itn int
#define coder goodboy
using namespace std;
typedef long long LL;typedef unsigned long long ULL;
const int maxn=32010,maxv=32020;
int n,v,w[maxn],f[maxv],c[maxn],w1[maxn],w2[maxn],c1[maxn],c2[maxn],temp1,temp2,temp3,cnt=1,Max=-1;
inline void in(){
	freopen("budget.in","r",stdin);
	freopen("budget.out","w",stdout);
	scanf("%d%d",&v,&n);v/=10;
	for (int i=1;i<=n;i++){
		scanf("%d%d%d",&temp1,&temp2,&temp3);temp1/=10;
		if (!temp3){
			w[i]=temp1*temp2;c[i]=temp1;
		}
		else {
			if (!w1[temp3]){
				w1[temp3]=temp1*temp2;c1[temp3]=temp1;
			}
			else{
				w2[temp3]=temp1*temp2;c2[temp3]=temp1;
			}
		}
	}
}
inline void dp(){
	for (int k=1;k<=n;k++){
		for (int V=v;V>=c[k];V--){
			f[V]=max(f[V],f[V-c[k]]+w[k]);
			if (c[k]+c1[k]<=V) f[V]=max(f[V],f[V-c[k]-c1[k]]+w[k]+w1[k]);
			if (c[k]+c2[k]<=V) f[V]=max(f[V],f[V-c[k]-c2[k]]+w[k]+w2[k]);
			if (c[k]+c1[k]+c2[k]<=V) f[V]=max(f[V],f[V-c[k]-c1[k]-c2[k]]+w[k]+w1[k]+w2[k]);
			Max=max(Max,f[V]);
		}
	}
}
inline void pr(){
	printf("%d",f[v]*10);
}
int Main(){
	in();
	dp();
	pr();
	return 0;
}
int main(){;}
int goodboy=Main();