记录编号	160074	评测结果	AAAAAAAAAAAAAA
题目名称	守卫标志物	最终得分	100
用户昵称	ggwdwsbs	是否通过	通过
代码语言	C++	运行时间	1.585 s
提交时间	2015-04-23 19:08:47	内存使用	32.29 MiB

/*
f[s] 在s状态下最大的安全因子
h[s] 在s状态下的高度
w[s] 在s状态下的重量 
状态转移方程  ：  f[s] = max( f[s]  , f[s] )
                  w[s] =  w[s] + weight[]
                  h[s] =  h[s] + high[]
*/
#include<stdio.h>
#include<cstring>
#define LL long long
const int maxn=101;
const LL INF=1e18;
LL f[(1<<21)];
int height[maxn];
int force[maxn];
int weight[maxn];
//int w[maxn];
LL h[(1<<21)];
int n;
LL H;
LL min(LL x,LL y)
{
	if(x>y) return y;
	else return x; 
}
LL max(LL x,LL y)
{
	if(x>y) return x;
	else return y;
}
LL maxx=-INF;
int main()
{
	freopen("guardc.in","r",stdin);
	freopen("guardc.out","w",stdout);
	scanf("%d%lld",&n,&H);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&height[i],&weight[i],&force[i]);
	memset(f,-1,sizeof(f));
	f[0]=INF;
	for(int s=1;s<(1<<n);s++)
	{
		for(int i=1;i<=20;i++)
		 if((s>>(i-1))%2==1)
		 {
		 	 int t=s^(1<<(i-1));
			 if(weight[i]>f[t]) continue;
			 h[s]=h[t]+height[i];
			 f[s]=max(f[s],min(f[t]-weight[i],force[i]));
		 }
		if(h[s]>=H) maxx=max(maxx,f[s]);	
	}
	if(maxx==-INF) printf("Mark is too tall");
	else printf("%lld",maxx);
}