$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 total + $w[depth] if total + $w[depth] == $nerai return total if total == $nerai return -1 end $dp[depth+1][total+$w[depth]] = dfs(depth+1, total+$w[depth]) if $dp[depth+1][total+$w[depth]].nil? $dp[depth+1][total] = dfs(depth+1, total) if $dp[depth+1][total].nil? return $dp[depth+1][total+$w[depth]] if $nerai == $dp[depth+1][total+$w[depth]] return $dp[depth+1][total] if $nerai == $dp[depth+1][total] return -1 end puts dfs(-1, 0) > 0 ? "possible" : "impossible"