program yukicoder_4 use, intrinsic :: iso_fortran_env implicit none integer(int32) :: n, sum_w integer(int32), allocatable :: ws(:) logical, allocatable :: dp(:, :) integer(int32) :: i, j, bef read(input_unit, *) n allocate(ws(n)) read(input_unit, *) ws(:) sum_w = sum(ws(:)) if (iand(sum_w, b'1') == 1) then write(output_unit, '(a)') "impossible" stop end if !> sum_w is even. allocate(dp(0:sum_w / 2, 0:n), source = .false.) dp(0, 0) = .true. do i = 1, n dp(:, i) = dp(:, i - 1) do j = 0, sum_w / 2 bef = j - ws(i) if (bef < 0) cycle !> bef >= 0 if (.not. dp(bef, i - 1)) cycle dp(j, i) = .true. end do end do write(output_unit, '(a)') trim(merge("possible ", "impossible", dp(sum_w / 2, n))) end program yukicoder_4