defmodule Main do def main do n = IO.read(:line) |> String.trim() |> String.to_integer() wn = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1) solve(n, wn) |> IO.puts() end def solve(n, wn) do with sum <- Enum.sum(wn), 0 <- rem(sum, 2) do max = round(sum / 2) dp = %{ 0 => 0..max |> Enum.reduce(%{}, &Map.put(&2, &1, 0))} wn |> Enum.with_index() |> Enum.reduce(dp, fn {w, i}, dp -> dp_i = 0..max |> Enum.reduce(dp[i], fn j, acc -> dp_j = if w <= j do max(dp[i][j - w] + w, dp[i][j]) else dp[i][j] end Map.put(acc, j, dp_j) end) Map.put(dp, i + 1, dp_i) end) |> (fn dp -> dp[n][max] end).() |> Kernel.==(max) |> if do :possible else :impossible end else _ -> :impossible end end end