#849581 (Go) No.4 おもりと天秤

• 問題: No.4 おもりと天秤
• ユーザー: 草苺奶昔
• 提出日時: 2023-03-16 13:07:20
• 言語: Go (1.22.1)
• 結果: AC
• 実行時間: 2 ms / 5,000 ms
• コード長: 1,991 bytes
• コンパイル時間: 11,634 ms
• コンパイル使用メモリ: 231,904 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-18 09:19:10
• 合計ジャッジ時間: 12,551 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	1 ms; 5,376 KB
testcase_21	AC	1 ms; 5,376 KB
testcase_22	AC	1 ms; 5,376 KB

ソースコード

// 可能的子集和
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	fmt.Fscan(in, &n)
	nums := make([]int, n)
	sum := 0
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &nums[i])
		sum += nums[i]
	}

	_, ok := subsetSum(nums, sum/2)
	can := ok || sum == 0
	if can && sum%2 == 0 {
		fmt.Fprintln(out, "possible")
	} else {
		fmt.Fprintln(out, "impossible")
	}
}

// 能否用nums中的若干个数凑出和为target
//  O(n*max(nums)))
func subsetSum(nums []int, target int) (res []int, ok bool) {
	if target <= 0 {
		return
	}

	n := len(nums)
	max_ := 0
	for _, v := range nums {
		max_ = max(max_, v)
	}
	right, curSum := 0, 0
	for right < n && curSum+nums[right] <= target {
		curSum += nums[right]
		right++
	}
	if right == n && curSum != target {
		return
	}

	offset := target - max_ + 1
	dp := make([]int, 2*max_)
	for i := range dp {
		dp[i] = -1
	}
	pre := make([][]int, n)
	for i := range pre {
		pre[i] = make([]int, 2*max_)
		for j := range pre[i] {
			pre[i][j] = -1
		}
	}

	dp[curSum-offset] = right
	for i := right; i < n; i++ {
		ndp := make([]int, len(dp))
		copy(ndp, dp)
		p := pre[i]
		a := nums[i]
		for j := 0; j < max_; j++ {
			if ndp[j+a] < dp[j] {
				ndp[j+a] = dp[j]
				p[j+a] = -2
			}
		}
		for j := 2*max_ - 1; j >= max_; j-- {
			for k := ndp[j] - 1; k >= max(dp[j], 0); k-- {
				if ndp[j-nums[k]] < k {
					ndp[j-nums[k]] = k
					p[j-nums[k]] = k
				}
			}
		}
		dp = ndp
	}

	if dp[max_-1] == -1 {
		return
	}

	used := make([]bool, n)
	i, j := n-1, max_-1
	for i >= right {
		p := pre[i][j]
		if p == -2 {
			used[i] = !used[i]
			j -= nums[i]
			i--
		} else if p == -1 {
			i--
		} else {
			used[p] = !used[p]
			j += nums[p]
		}
	}

	for i >= 0 {
		used[i] = !used[i]
		i--
	}

	for i := 0; i < n; i++ {
		if used[i] {
			res = append(res, i)
		}
	}

	ok = true
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}