| 27 | ostream &operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) { cout << it << " "; } return ostream; } |
| 28 | |
| 29 | void solve() { |
| 30 | ll n, x; cin >> n >> x; |
| 31 | vector<ll> coins(n); |
| 32 | cin >> coins; |
| 33 | |
| 34 | vector<ll>prev(x + 1,0); |
| 35 | for (ll i = 0; i <= x; ++i) { |
| 36 | if (i % coins[0] == 0 ) prev[i] = i / coins[0]; |
| 37 | else prev[i] = 1e9; |
| 38 | } |
| 39 | for (ll i = 1; i < n; ++i) { |
| 40 | vector<ll > cur(x + 1, 0); |
| 41 | for (ll tar = 1; tar <= x; ++tar) { |
| 42 | ll take = 1e9; |
| 43 | if (tar >= coins[i]) take = cur[tar-coins[i]] + 1; |
| 44 | ll notake = prev[tar]; |
| 45 | cur[tar] = min(take,notake); |
| 46 | } |
| 47 | prev = cur; |
| 48 | } |
| 49 | cout << (prev[x] == 1e9 ? -1 : prev[x]) << '\n'; |
| 50 | } |
| 51 | |
| 52 | signed main() { |
| 53 | ios_base::sync_with_stdio(false),cin.tie(nullptr); |