比赛 |
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