Saleh127

Light oj(LO) 1235

Oct 6th, 2020 (edited)
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. vector<ll>ans;
  6. void allcmbntn(ll ind,vector<ll>x,ll sum=0)
  7. {
  8. if(ind==x.size())
  9. {
  10. ans.push_back(sum);
  11. return;
  12. }
  13. allcmbntn(ind+1,x,sum);
  14. allcmbntn(ind+1,x,sum+x[ind]);
  15. allcmbntn(ind+1,x,sum+(2*x[ind]));
  16. }
  17.  
  18. int main()
  19. {
  20. ios_base::sync_with_stdio(0);
  21. cin.tie(0);
  22. cout.tie(0);
  23.  
  24. test
  25. {
  26. ll n,w,c,i,k;
  27.  
  28. cin>>n>>w;
  29. vector<ll>a,a1;
  30. for(i=1; i<=n; i++)
  31. {
  32. cin>>c;
  33. if(i<=(n/2))
  34. {
  35. a.push_back(c);
  36. }
  37. else
  38. {
  39. a1.push_back(c);
  40. }
  41. }
  42.  
  43. ans.clear();
  44. allcmbntn(0,a);
  45. a=ans;
  46.  
  47. ans.clear();
  48. allcmbntn(0,a1);
  49. a1=ans;
  50.  
  51. sort(a1.begin(),a1.end());
  52. sort(a.begin(),a.end());
  53. k=0;
  54.  
  55. for(i=0;i<a.size();i++)
  56. {
  57. k=binary_search(a1.begin(),a1.end(),w-a[i]);
  58. if(k) break;
  59. }
  60.  
  61. if(k) cout<<"Case "<<cs<<": Yes"<<endl;
  62. else cout<<"Case "<<cs<<": No"<<endl;
  63. }
  64.  
  65. return 0;
  66. }
  67.  
Add Comment
Please, Sign In to add comment