結果

問題 No.4 おもりと天秤
コンテスト
ユーザー vjudge1
提出日時 2025-09-04 16:51:18
言語 Crystal
(1.14.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 612 bytes
コンパイル時間 14,814 ms
コンパイル使用メモリ 310,000 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-04 16:51:35
合計ジャッジ時間 15,173 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = gets.not_nil!.to_i
w = gets.not_nil!.split.map(&.to_i)

# if w.size != n
#   puts "Error: Expected #{n} numbers but got #{w.size}"
#   exit
# end

t = w.sum
if t.odd?
  puts "impossible"
  exit
end

th = t // 2

# Create a 2D array with n+1 rows and th+1 columns, initialized to 0
m = Array(Array(Int32)).new(n + 1) { Array(Int32).new(th + 1, 0) }

(1...n).each do |i|
  (0..th).each do |j|
    if j < w[i]
      m[i][j] = m[i - 1][j]
    else
      m[i][j] = Math.max(m[i - 1][j - w[i]] + w[i], m[i - 1][j])
    end

    if m[i][j] == th
      puts "possible"
      exit
    end
  end
end

puts "impossible"
0