1917F - Construct Tree - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define oo 1000000010
#define mod 998244353
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define getrand(l, r) uniform_int_distribution<int>(l, r)(rng)

const int N = 2010;

int n , d;

int l[N];

bitset < N > dp[2][N];
 
 
void solve(){
	scanf("%d%d",&n,&d);
	for(int i = 0 ;i < n;i++){
		scanf("%d",&l[i]);
	}
	sort(l , l + n);
	reverse(l , l + n);
	if(l[0] + l[1] > d){
		puts("No");
		return;
	}
	for(int i = 0;i <= d;i++){
		dp[n & 1][i] = 0;
	}
	dp[n & 1][0][0] = 1;

	for(int cur , nxt , i = n - 1;i > 0;i--){
		cur = (i & 1);
		nxt = (cur ^ 1);
		for(int j = 0 ;j <= d;j++){
			dp[cur][j] = dp[nxt][j];
			if(j >= l[i]){
				dp[cur][j] |= (dp[nxt][j - l[i]]);
				dp[cur][j] |= (dp[nxt][j - l[i]] << l[i]);
			}
		}
	}
	for(int cur , i = 0 ;i <= d;i++){
		if(dp[1][d][i]){
			cur = min(i , d - i);
			if(cur >= l[0]){
				puts("Yes");
				return;
			}

		}
	}

	dp[0][d] = dp[1][d - l[0]];
	//cout << dp[0][d] << endl;
	for(int i = 0 ;i <= d;i++){
		if(dp[0][d][i]){
			puts("Yes");
			return;
		}
	}

	puts("No");
	 
}

int main() {
	int t;
	scanf("%d",&t);
	while(t--)
		solve(); 
	return 0;
}