Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <stdio.h>
  5. #include <algorithm>
  6. #include <set>
  7. #include <map>
  8. #include <math.h>
  9. #include <cmath>
  10. #include <queue>
  11. #include <iomanip>
  12. #include <bitset>
  13. #include <memory.h>
  14. using namespace std;
  15.  
  16. const int INF = 1e+9;
  17.  
  18. int main(){
  19. ios_base::sync_with_stdio(false);
  20. int n, s;
  21. cin >> n;
  22. vector <int> v(n);
  23. for (int i=0; i<n; ++i)
  24. cin >> v[i];
  25. cin >> s;
  26. vector <int> d(s+1);
  27. d[0] = 0;
  28. for (int m=1; m<=s; ++m){
  29. d[m] = INF;
  30. for (int i=0; i<n; ++i){
  31. if (m >= v[i] && d[m - v[i]] + 1 < d[m]){
  32. d[m] = d[m - v[i]] + 1;
  33. }
  34. }
  35. }
  36. if (d[s] == INF)
  37. cout << "No solution";
  38. else{
  39. vector <int> ans;
  40. while (s > 0)
  41. for (int i=0; i<n; ++i){
  42. if (s - v[i] >= 0 && d[s - v[i]] == d[s]-1){
  43. ans.push_back(v[i]);
  44. s -= v[i];
  45. break;
  46. }
  47. }
  48. reverse(ans.begin(), ans.end());
  49. for (int i=0; i<ans.size(); ++i)
  50. cout << ans[i] << " ";
  51. }
  52. return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement