結果

問題 No.10 ＋か×か
コンテスト
ユーザー neko_the_shadow
提出日時 2019-05-29 16:33:19
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 569 bytes
コンパイル時間 71 ms
コンパイル使用メモリ 7,680 KB
実行使用メモリ 52,096 KB
最終ジャッジ日時 2024-09-17 15:59:09
合計ジャッジ時間 5,604 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

n = gets.to_i
t = gets.to_i
a = gets.split.map(&:to_i)

# +: 0
# *: 1
# pass: inf
dp = Array.new(n + 1){ Array.new(t + 1, Float::INFINITY) }
dp[1][a[0]] = -1
(1...n).each do |x|
  (0..t).each do |y|
    next if dp[x][y] == Float::INFINITY
    dp[x + 1][y + a[x]] = [dp[x + 1][y + a[x]], 0].min if y + a[x] <= t
    dp[x + 1][y * a[x]] = [dp[x + 1][y * a[x]], 1].min if y * a[x] <= t
  end
end

stack = []
n.downto(2).each do |x|
  op = dp[x][t]
  if op == 0
    stack << "+"
    t -= a[x - 1]
  else
    stack << "*"
    t /= a[x - 1]
  end
end

puts stack.reverse.join
0