use proconio::{input, fastout}; use std::cmp::max; #[fastout] fn main() { input! { N: usize, W: usize, v: [u32; N], w: [usize; N], } let ans = solve(N, W, &v, &w); println!("{}", ans.len()); if !ans.is_empty() { let s = ans.iter().map(|x| x.to_string()).collect::>().join(" "); println!("{}", s); } else { println!(); } } fn solve(N: usize, W: usize, v: &[u32], w: &[usize]) -> Vec { let mut dp: Vec> = vec![vec![0u32; W + 1]; N + 1]; for i in (0..N).rev() { let wi = w[i]; for j in 0..wi.min(W + 1) { dp[i][j] = dp[i + 1][j]; } for j in wi..=W { dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - wi].saturating_add(v[i])); } } let mut ans: Vec = Vec::with_capacity(N); let mut j = W; for i in 0..N { if dp[i][j] != dp[i + 1][j] { ans.push((i + 1) as u32); j = j.saturating_sub(w[i]); } } ans }