提出 #67506631

---

ソースコード 拡げる

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

// 経路復元のための構造体
type State struct {
	idx  int // 使用したカードのインデックス
	prev int // そのときの前の合計値
}

// main関数：標準入力を読み取り、部分和の存在判定と経路出力を行う
func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	header := strings.Split(scanner.Text(), " ")
	N, _ := strconv.Atoi(header[0])
	S, _ := strconv.Atoi(header[1])

	scanner.Scan()
	parts := strings.Split(scanner.Text(), " ")
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i], _ = strconv.Atoi(parts[i])
	}

	// dp[sum] = State：sumを作るのにどのカードを使ったかとその前のsumを記録
	dp := make(map[int]State)
	dp[0] = State{-1, -1} // 0は何も使わずに作れる

	for i := 0; i < N; i++ {
		nextDP := make(map[int]State)
		for s := range dp { // ✅ 未使用変数stを削除
			newSum := s + A[i]
			if newSum <= S {
				if _, exists := dp[newSum]; !exists {
					nextDP[newSum] = State{i, s}
				}
			}
		}
		for k, v := range nextDP {
			dp[k] = v
		}
	}

	if _, ok := dp[S]; !ok {
		fmt.Println(-1)
		return
	}

	// 経路復元
	res := []int{}
	curr := S
	for curr != 0 {
		state := dp[curr]
		res = append(res, state.idx+1) // 1-indexed
		curr = state.prev
	}

	// 逆順にして出力
	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}

	fmt.Println(len(res))
	for i, v := range res {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Print(v)
	}
	fmt.Println()
}

提出情報

ジャッジ結果