Untitled

 avatar
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...