#include<bits/stdc++.h>
#define int long long
#define I_love_ch ios::sync_with_stdio(0)
#define China cin.tie(0)
#define France cout.tie(0)
#define ch_France return 0
using namespace std;
struct node{
	int h,w,s;
}a[1000010];
bool cmp(node x,node y){
	return x.w+x.s<y.w+y.s;
}
int n,h,f[(1<<25)+10],dp[(1<<25)+10],ans=-1;
signed main(){
  freopen("block.in","r",stdin);
	freopen("block.out","w",stdout);
	I_love_ch;
	China;
	France;
	cin>>n>>h;
	for(int i=1;i<=n;i++){
		cin>>a[i].h>>a[i].w>>a[i].s;
	}
	sort(a+1,a+n+1,cmp);
	f[0]=1e10;
	for(int mask=0;mask<(1<<n);mask++){
		if(mask==0) continue;
		int last=__builtin_ffs(mask);
		dp[mask]=dp[mask^(1<<(last-1))]+a[last].h;
		f[mask]=min(f[mask^(1<<(last-1))]-a[last].w,a[last].s);
		if(dp[mask]>=h) ans=max(ans,f[mask]);
	}
	if(ans==-1) cout<<"Impossible\n";
	else cout<<ans<<"\n";
	ch_France;
}

2 条评论

  • @ 2026-9-15 11:50:20

    你说的很对,但是洛谷上过了,确实是MLE,调不出来了

    🤡 1
    👀 1
    🕊️ 1
    🍋 1
    🌿 1
    🤣 1
    🤔 1
    ❤️ 1
    😕 1
    😄 1
    👎 1
    👍 1
    • @ 2026-9-11 8:35:03

      MLE

      • 1

      信息

      ID
      581
      时间
      1000ms
      内存
      256MiB
      难度
      9
      标签
      (无)
      递交数
      127
      已通过
      7
      上传者