Advertisement
OMEGAHEAD_MonkoX

Untitled

Mar 30th, 2020
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string>
  4. #include <sstream>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <stdlib.h>
  8. #include <stdio.h>
  9. #include <fstream>
  10. #include <stack>
  11. #include <map>
  12. #include <cstring>
  13. #include <cmath>
  14. #include <set>
  15. #include <iterator>
  16. #include <cmath>
  17. #include <locale>
  18. #include <queue>
  19. #include <deque>
  20. #include <stack>
  21.  
  22.  
  23. using namespace std;
  24.  
  25.  
  26.  
  27. const int MOD = 1e6+7;
  28.  
  29.  
  30. int main()
  31. {
  32. long long int N, n, a;
  33. cin >> N >> n;
  34. vector<long long int> vec;
  35. for (auto i = 0; i < N; ++i)
  36. {
  37. cin >> a;
  38. vec.push_back(a);
  39. }
  40. vector<vector<long long int> > vec2(vec.size() + 1, vector<long long int> (n + 1, 0));
  41. for (auto i = 1; i < n + 1; ++i)
  42. {
  43. if (i >= vec[0])
  44. {
  45. vec2[0][i] = vec[0];
  46. }
  47. }
  48.  
  49. for (auto i = 1; i < vec.size(); ++i)
  50. {
  51. for(auto j = 1; j < n + 1; ++j)
  52. {
  53. if (j < vec[i])
  54. vec2[i][j] = vec2[i - 1][j];
  55. else
  56. vec2[i][j] = max(vec2[i - 1][j], vec[i] + vec2[i - 1][j - vec[i]]);
  57. }
  58. }
  59. if (vec2[vec.size() - 1][n] == n)
  60. {
  61. cout << "YES";
  62. return 0;
  63. }
  64. cout << "NO";
  65. return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement