Submission #2241052

---

Source Code Expand

N,Ma,Mb=map(int,input().split())
Med=[]
for i in range(N):
  a=[int(x) for x in input().split()]
  Med.append(a)
  
#[i]まででMa=[j],Mb=[k]を作る場合の最小のコストdp
#dp[i+1][j+Ma][k+Mb]=min(dp[i][j+Ma][k+Mb],dp[i][j][k]+Cost)
#リストをinfで初期化。inf=作れない配合なので、continue。初期値はdp[0][0][0]=0
dp=[[[float('inf') for j in range(401)] for k in range(401)] for i in range(N+1)]
dp[0][0][0]=0

for i in range(N):
  for j in range(401):
    for k in range(401):
      if dp[i][j][k]==float('inf'):
        continue
      dp[i+1][j][k]=min(dp[i][j][k],dp[i+1][j][k])
      dp[i+1][j+Med[i][0]][k+Med[i][1]]=min(dp[i][j+Med[i][0]][k+Med[i][1]],dp[i][j][k]+Med[i][2])

ans=float('inf')
for i in range(1,N+1):
  if i*Ma<401 and i*Mb<401:
    ans=min(ans,dp[N][i*Ma][i*Mb])
if ans==float('inf'):
  print(-1)
else:
  print(ans)

Submission Info

Judge Result