Golfe

golfe.cpp

// solucao por Bruno Mello

#include <bits/stdc++.h>

using namespace std;

const int N=100002;
const int inf=0x3f3f3f3f;

int v[N];
int n,d;
int dp[N], u[N], dp2[N];

bool possivel(int d){
  if(d==0)return 1;
  if(d<0)return 0;
  if(dp[d]>=0)return dp[d];
  for (int i=1;i<=n;i++){
    if(possivel(d-v[i])==1) return dp[d]=1;
  }
  return dp[d]=0;
}

int solve(int d){
  if(d==0)return 0;
  if(d<0)return inf;
  if(dp2[d] >= 0) return dp2[d]
  int menor=inf;
  for (int i=1;i<=n;i++){
    menor=min(menor,solve(d-v[i]));
  }
  return dp2[d] = menor+1;
}

int main()
{
  cin >> n >> d;
  memset(dp,-1,sizeof(dp));
  memset(dp2, -1, sizeof(dp2));
  for (int i=1;i<=n;i++){
    scanf("%d", &v[i]);
  }
  if(possivel(d)==0){
    printf("-1\n");
    return 0;
  }
  printf("%d\n", solve(d));
  return 0;
}