Untitled
unknown
c_cpp
2 years ago
928 B
5
Indexable
#include <bits/stdc++.h> #define ll long long using namespace std ; const int maxn = 1e6+7; ll dp[maxn]; int c[maxn]; void dbg(){ cerr << endl; } template<typename H, typename... T> void dbg(H h, T... t){ cerr << h << ", "; dbg(t...); } #define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__) int main(){ int a, b; cin >> a >> b; for(int i = 0; i <= b ; i++){ dp[i] = 0; } for(int i = 0 ; i < a; i++){ cin >> c[i]; dp[c[i]] = 1; } ll res; for(int i = 1 ; i <= b ; i++){ res = 1e16 ; for(int j = 0 ; j < a ; j++){ if(i - c[j] < 0 || dp[i] == 1) continue; res = min(dp[i-c[j]] , res); if(dp[i-c[j]]!=0){ dp[i] = res+1; } } } if(dp[b] == 0) cout << -1; else cout << dp[b]; return 0; }
Editor is loading...