# Here your code ! def solve(w, t) dp = {} dp[0] = Array.new(w.size + 1, 0) (1..t).each do |j| dp[j] = Array.new(w.size + 1, 0) w.each_with_index do |k, i| candiate = [dp[j][i], dp[j][i] + k ] candiate.push(dp[j - k][i] + k) if j >= k candiate.reject! {|v| v > j } dp[j][i + 1] = candiate.max end end dp[t].include?(t) end n = gets.to_i w = gets.split.map(&:to_i) total = w.inject(0, &:+) if total.odd? puts "impossible" elsif solve(w,total/2) puts "possible" else puts "impossible" end