Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int main() {
- int n ,s; cin>>n>>s;
- int* arr = new int[n]();
- for(int i = 0; i<n; ++i) cin>>arr[i];
- bool** dp = new bool*[2]();
- for(int i =0; i< 2; ++i) dp[i] = new bool[s+1];
- for(int i = 0; i<=s; ++i) dp[0][i] = false;
- dp[0][0] = true;
- int flag = 1;
- for(int i = 1; i<=n; ++i){
- for(int j = 1; j<=s; ++j) {
- dp[flag][j] = dp[flag^1][j];
- if(j >= arr[i-1]) dp[flag][j] = dp[flag][j] || dp[flag^1][j-arr[i]];
- }
- flag = flag^1;
- }
- if(dp[flag^1][s]) cout<<"Yes"<<endl;
- else cout<<"No"<<endl;
- }
Add Comment
Please, Sign In to add comment