Submission #1519038

---

Source Code Expand

INF = 1 << 30
n, ma, mb = gets.not_nil!.split.map(&.to_i)
p = Array.new(n) { gets.not_nil!.split.map(&.to_i) }
dp = Array.new(n * 10 + 1) { Array.new(n * 10 + 1, INF) }
dp[0][0] = 0
n.times do |i|
  a = p[i][0]
  b = p[i][1]
  c = p[i][2]
  (dp.size - 1).downto(a) do |j|
    (dp.size - 1).downto(b) do |k|
      next if dp[j - a][k - b] == INF
      dp[j][k] = {dp[j][k], dp[j - a][k - b] + c}.min
    end
  end
end
ans = INF
(1...dp.size).each do |i|
  (1...dp.size).each do |j|
    ans = {ans, dp[i][j]}.min if i * mb == j * ma
  end
end
puts ans == INF ? -1 : ans

Submission Info

Judge Result