Submission #2241076

---

Source Code Expand

N,Ma,Mb=map(int,input().split())
Med=[]
cnt_a=0
cnt_b=0
for i in range(N):
  a=[int(x) for x in input().split()]
  Med.append(a)
  cnt_a+=a[0]
  cnt_b+=a[1]
  
#[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(cnt_b+1)] for k in range(cnt_a+1)] for i in range(N+1)]
dp[0][0][0]=0

for i in range(N):
  for j in range(cnt_a+1):
    for k in range(cnt_b+1):
      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