Guest User

Untitled

a guest
Jan 18th, 2020
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.58 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. int main() {
  4. int n ,s; cin>>n>>s;
  5. int* arr = new int[n]();
  6. for(int i = 0; i<n; ++i) cin>>arr[i];
  7. bool** dp = new bool*[2]();
  8. for(int i =0; i< 2; ++i) dp[i] = new bool[s+1];
  9. for(int i = 0; i<=s; ++i) dp[0][i] = false;
  10. dp[0][0] = true;
  11. int flag = 1;
  12. for(int i = 1; i<=n; ++i){
  13. for(int j = 1; j<=s; ++j) {
  14.  
  15. dp[flag][j] = dp[flag^1][j];
  16. if(j >= arr[i-1]) dp[flag][j] = dp[flag][j] || dp[flag^1][j-arr[i]];
  17. }
  18. flag = flag^1;
  19. }
  20.  
  21. if(dp[flag^1][s]) cout<<"Yes"<<endl;
  22. else cout<<"No"<<endl;
  23.  
  24. }
Add Comment
Please, Sign In to add comment