Advertisement
Guest User

Untitled

a guest
Jan 20th, 2020
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.71 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 1e8;
  4. long long dp[1000010];
  5. int main() {
  6. int n;
  7. vector<int> ans;
  8. cin >> n;
  9. int a[n + 10];
  10. for (int i = 1; i <= n; ++i)
  11. cin >> a[i];
  12. sort(a + 1, a + 1 + n);
  13. int s;
  14. cin >> s;
  15. for (int i = 1; i <= s; ++i) {
  16. dp[i] = INF;
  17. for (int j = 1; j <= n; ++j)
  18. if (i >= a[j] && dp[i - a[j]] + 1 < dp[i])
  19. dp[i] = dp[i - a[j]] + 1;
  20. }
  21. if (dp[s] == INF) {
  22. cout << "No solution";
  23. return 0;
  24. }
  25. else {
  26. while(s > 0)
  27. for(int i = 1; i <= n; ++i)
  28. if (dp[s - a[i]] + 1 == dp[s]) {
  29. cout << a[i] << ' ';
  30. s -= a[i];
  31. break;
  32. }
  33. }
  34. return 0;
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement