比赛 20150423 评测结果 AWATTTATTTTTTT
题目名称 守卫标志物 最终得分 21
用户昵称 wolf. 运行时间 10.025 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2015-04-23 11:44:59
显示代码纯文本
#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
class node{
public:
	int h,w,k;
	node(){
	}
	node(int a,int b,int c){
		h=a;
		w=b;
		k=c;
	}
};
const int IMAX=999999999;
vector<node> TT;
vector<bool> flag;
long long mmax=-1,h;
void work(long long hh,long long ww,long long kk){
	//cout<<hh<<"  "<<ww<<"  "<<kk<<endl;
	//hh表示当前高度
	//ww表示当前的堆的部分重量
	//kk表示现在堆中最大限制重量
	for(int i=0;i!=TT.size();++i){//向上累加一个还未累加的牛
		//cout<<i<<" "<<TT[i].w<<endl;
		if(flag[i]||ww+TT[i].w>kk){
			continue;
		}
		if(hh+TT[i].h>=h){//如果累加后高度不小于h
			long long mmin;
			mmin=min(kk-ww-TT[i].w,(long long)(TT[i].k));
			//计算下层的最大限重和本层加上后的重量差  普通情况是下面的可以支撑最上面的且不受最上层限制
			//计算这只牛累加后他的限制重量 最上层限制了再往上的大小
			//计算这两个哪个更小
			mmax=max(mmax,mmin); 
			//cout<<ok<<"  "<<mmax<<endl;
			//cout<<"back"<<endl;
			continue;
		}
		//cout<<"beg   "<<i<<endl;
		flag[i]=1;
		if(TT[i].k<kk){//玻璃心  ||  第一个
			work(TT[i].h+hh,0,TT[i].k);
		}else{
			work(TT[i].h+hh,ww+TT[i].w,kk);
		}
		flag[i]=0;
	}
	//cout<<"back"<<endl;
}
int core(){
	flag.resize(TT.size(),0);
	work(0,0,IMAX);//大地
	//cout<<mmax<<endl;
	return mmax;
}
int main(){
	int n;
	fin>>n>>h;
	for(int i=0;i!=n;++i){
		int a,b,c;
		fin>>a>>b>>c;
		TT.push_back(node(a,b,c));
	}
	int r=core();
	if(r>=0){
		fout<<r<<endl;
	}else{
		fout<<"Mark is too tall"<<endl;
	}
	//-------------------------*/
	#if defined wolf
	cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
	#endif
	return 0;
}
//Designed by wolf
//Thu Apr 23 2015