Saleh127

UVA 10664

May 2nd, 2021
204
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.96 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main()
  5. {
  6.  
  7. int t;
  8. cin>>t;
  9. getchar();
  10. for(int cs=1; cs<=t; cs++)
  11. {
  12.  
  13. string a;
  14. getline(cin,a);
  15.  
  16. ll n,m,i,j,k=0,l=0;
  17. vector<ll>x;
  18.  
  19. for(i=0; i<a.size(); i++)
  20. {
  21. if(a[i]==' ')
  22. {
  23. x.push_back(k);
  24. l+=k;
  25. k=0;
  26. }
  27. else
  28. {
  29. k=(k*10)+(a[i]-'0');
  30. }
  31. }
  32.  
  33. l+=k;
  34.  
  35. if(k) x.push_back(k);
  36.  
  37. ll dp[2000]={0};
  38.  
  39. dp[0]=1;
  40.  
  41. for(i=0; i<x.size(); i++)
  42. {
  43. for(j=(l/2); j>=0; j--)
  44. {
  45. if(dp[j])
  46. {
  47. dp[j+x[i]]=1;
  48. }
  49. }
  50. }
  51. if(dp[(l/2)]==1 && l%2==0) cout<<"YES"<<endl;
  52. else cout<<"NO"<<endl;
  53.  
  54. }
  55.  
  56. return 0;
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment