結果

問題 No.4 おもりと天秤
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-16 13:07:20
言語 Go
(1.22.1)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,991 bytes
コンパイル時間 14,258 ms
コンパイル使用メモリ 213,008 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-18 12:59:16
合計ジャッジ時間 13,397 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 1 ms
4,348 KB
testcase_07 AC 1 ms
4,348 KB
testcase_08 AC 1 ms
4,348 KB
testcase_09 AC 1 ms
4,348 KB
testcase_10 AC 1 ms
4,348 KB
testcase_11 AC 1 ms
4,348 KB
testcase_12 AC 1 ms
4,348 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 1 ms
4,348 KB
testcase_16 AC 1 ms
4,348 KB
testcase_17 AC 1 ms
4,348 KB
testcase_18 AC 2 ms
4,348 KB
testcase_19 AC 1 ms
4,348 KB
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 2 ms
4,348 KB
testcase_22 AC 1 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 可能的子集和
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
}
0