记录编号	159988	评测结果	AAAAAAAAAAAAAA
题目名称	守卫标志物	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	2.222 s
提交时间	2015-04-23 15:46:18	内存使用	16.31 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#include <string.h>
#define LL long long
using namespace std;
ifstream in("guardc.in");
ofstream out("guardc.out");
LL n;
LL He=0;
LL best=0;
LL H[1<<20],M[1<<20];
LL ans=-1000;
LL INF=0x7fffffff;
class node
{
public:
	LL G;
	LL H;
	LL F;
}cow[21];
bool com(node a,node b)
{
	//out<<a.F<<' '<<b.F<<endl;
	if(a.F>b.F)return 1;
	if(a.F==b.F)
	{
		if(a.H<b.H)return 1;
		if(a.H==b.H)
		{
			if(a.G>b.G)return 1;
		}
	}
	return 0;
}
int main()
{
	int i,j;
	in>>n;
	in>>He;
	for(i=0;i<n;i++)in>>cow[i].H>>cow[i].G>>cow[i].F;
	sort(cow+1,cow+n+1,com);
	M[0]=INF;
	for(i=0;i<(1<<n);i++)
	{
		for(j=0;j<n;j++)
		{
			if((i>>j)&1)
			{
				if(cow[j].G>M[i-(1<<j)])continue;
				H[i]=H[i-(1<<j)]+cow[j].H;
				M[i]=max(M[i],min(M[i-(1<<j)]-cow[j].G,cow[j].F));
			}
		}
		if(H[i]>=He)ans=max(ans,M[i]);
	}
	if(ans<0)out<<"Mark is too tall"<<endl;
	else out<<ans<<endl;
	return 0;
}