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

#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
#if defined wolf
const string ok="OK";
const string kk="	";
ofstream nnew("guardc.in",ios::app);
ifstream fin("guardc.in");
#define fout cout
#define Endl endl
#else
ifstream fin("guardc.in");
ofstream fout("guardc.out");
#endif
const int IMAX=999999999;
vector<int> HH;
vector<int> WW;
vector<int> KK;
vector<int> FF;
vector<int> SH;
int core(int n,int h){
	FF.resize((1<<n),-1);
	SH.resize((1<<n),0);
	int ans=-1;
	FF[0]=IMAX;
	int mm=(1<<n);
	for(int s=1;s<mm;++s){//给出所有的排列
		//cout<<bitset<10>(s)<<endl;
		for(int i=0;i<n;++i){//枚举第i头牛
			if((s>>i)&1){//s的第j个是 1
				int t=s^(1<<i);
				//cout<<i<<endl;
				if(WW[i]>FF[t]){
					continue;
				}
				FF[s]=max(FF[s],min(KK[i],FF[t]-WW[i]));
				SH[s]=SH[t]+HH[i];
			}
		}
		if(SH[s]>=h){
			ans=max(ans,FF[s]);
			//cout<<SH[s]<<endl;
		}
	}
	return ans;
}
int main(){
	int n,h;
	fin>>n>>h;
	for(int i=0;i!=n;++i){
		int a,b,c;
		fin>>a>>b>>c;
		//cout<<a<<kk<<b<<kk<<c<<endl;
		HH.push_back(a);
		WW.push_back(b);
		KK.push_back(c);
	}
	int r=core(n,h);
	if(r<0){
		fout<<"Mark is too tall"<<endl;
	}else{
		fout<<r<<endl;
	}
	//-------------------------*/
	#if defined wolf
	cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
	#endif
	return 0;
}
//Designed by wolf
//Thu Apr 23 2015