update on 26.09.10:

我发现了我的复杂度比别人多一个 $n$，也就是说，我是卡过去的。

SOLUTION

看到 $n \le 25$ 发现这个不大能直接暴力 dp，于是我们换个思路。

假如我们已经定好了要把集合 $S$ 里的元素放到这个大厦里，怎么放是最优的？

猜一下估计是一个贪心吧。

发现相邻两个积木的顺序不会影响他们前面或者后面所有元素的稳定值，于是我们可以试着邻项交换证一下。

于是通过非常简单的证明，得到一个式子：min(s-k.w,k.s)>min(k.s-w,s)。这个直接扔到重载的 $<$ 里面就行。

具体方法不说了。

发现这个有传递性，于是不需要对每一个集合排序，而是对全体积木排序就行了。

于是我们排序，枚举所有 $state \in [0,2^n-1]$，求出答案。

发现做完了，还是不难的。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,H;
struct node{
    int h,w,s;
    bool operator<(const node &k)const{
        return min(s-k.w,k.s)>min(k.s-w,s);
    }
}a[30];
#define lowbit(x) (x&(-x))
short mp[16777217];
signed main(){
    freopen("block.in","r",stdin);
    freopen("block.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>H;
    for(register int i=1;i<=n;i++){
        cin>>a[i].h>>a[i].w>>a[i].s;
    }
    for(int i=0;i<25;i++){
        mp[1<<i]=i+1;
    }
    sort(a+1,a+1+n);
    int ans=-1;
    for(register int i=1;i<(1<<n);i++){
        int s=i,hi=0,ms=1e18,t;
        while(s){
            t=mp[lowbit(s)],s-=lowbit(s),hi+=a[t].h,ms=min(ms-a[t].w,a[t].s);
        }
        if(hi<H||ms<0) continue;
        ans=max(ans,ms);
    }
    if(ans==-1) cout<<"Impossible\n";
    else cout<<ans<<'\n';
    return 0;
}

注：笔者发现了一种神奇的方法，使用 $lowbit$ 运算加速了枚举，有一点优化吧。

用以下代码进行测试发现快 $0.5$倍左右。

TESTCODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m;
int ppc(int x){
    int r=0;
    while(x) r+=(x&1),x>>=1;
    return r;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int ans=0;
    for(int i=1;i<=33554431;i++){
        ans+=ppc(i);
    }
    cout<<ans<<'\n';
    return 0;
}