Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
- #define ll long long
- #define scn(n) scanf("%d",&n)
- #define lscn(n) scanf("%lld",&n)
- #define lpri(n) printf("%lld",n)
- #define pri(n) printf("%d",n)
- #define pln() printf("\n")
- #define priln(n) printf("%d\n",n)
- #define lpriln(n) printf("%lld\n",n)
- #define rep(i,init,n) for(int i=init;i<n;i++)
- #define pb push_back
- #define mp make_pair
- #define F first
- #define S second
- #define gcd __gcd
- #define inf INT_MAX
- #define ninf INT_MIN
- const ll mod=1e9+7;
- const int N=1e4+4;
- int main()
- {
- int t;
- scn(t);
- //https://www.geeksforgeeks.org/subset-sum-problem-dp-25/(related standard problem)
- while(t--)
- {
- int n,x;
- scn(n); scn(x);
- int a[n],sum=0;
- rep(i,1,n+1)
- scn(a[i]),sum+=a[i];
- bool dp[n+1][N]; //dp[i][j] is 1 if it is possible to make a sum of j considering a subset first i items
- memset(dp,0,sizeof(dp));
- rep(i,0,n+1)
- dp[i][0]=1;
- rep(i,1,n+1)
- {
- rep(j,1,N)
- {
- dp[i][j]=dp[i-1][j];
- if(j-a[i]>=0)
- dp[i][j]|=dp[i-1][j-a[i]];
- }
- }
- int mn=inf;
- rep(i,0,sum+1)
- if(dp[n-1][i])
- {
- //cout<<i<<" ";
- int here=max(i,sum-i);
- mn=min(mn,here);
- }
- //cout<<endl;
- if(mn<=x)
- printf("YES\n");
- else
- printf("NO\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
