$n = gets.to_i $w = gets.split.map(&:to_i) $nerai = $w.inject(:+)/2.0 $dp = Array.new($n){Array.new(100*100+1, nil)} def dfs(depth, total) if depth >= $n - 1 return true if total + $w[depth] == $nerai return true if total == $nerai return false end $dp[depth+1][total+$w[depth]] ||= dfs(depth+1, total+$w[depth]) $dp[depth+1][total] ||= dfs(depth+1, total) return $dp[depth+1][total+$w[depth]] if $dp[depth+1][total+$w[depth]] return $dp[depth+1][total] if $dp[depth+1][total] return false end puts dfs(-1, 0) ? "possible" : "impossible"