結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー elphe
提出日時 2025-11-15 14:37:26
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 34 ms / 1,571 ms
コード長 1,251 bytes
コンパイル時間 12,739 ms
コンパイル使用メモリ 401,848 KB
実行使用メモリ 37,316 KB
最終ジャッジ日時 2025-11-15 14:37:43
合計ジャッジ時間 15,771 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 74
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        w: usize,
        value: [u32; n],
        weight: [u32; n],
    }

    println!(
        "{}",
        output(solve(
            n,
            w,
            value.into_iter().zip(weight).collect::<Vec<_>>()
        ))
    );
}

fn solve(n: usize, w: usize, items: Vec<(u32, u32)>) -> Vec<u32> {
    let mut dp = vec![[0; 3001]; 3001];
    for (i, (value, weight)) in items.iter().enumerate().rev() {
        for j in 0..*weight as usize {
            dp[i][j] = dp[i + 1][j];
        }
        for j in (*weight as usize)..=w {
            dp[i][j] = dp[i + 1][j].max(dp[i + 1][j - *weight as usize] + value);
        }
    }

    let dp = dp;
    let mut ans = Vec::with_capacity(n);
    let mut rest_weight = w;
    for (i, (_, weight)) in items.into_iter().enumerate() {
        if dp[i][rest_weight] != dp[i + 1][rest_weight] {
            ans.push((i + 1) as u32);
            rest_weight -= weight as usize;
        }
    }
    ans
}

fn output(ans: Vec<u32>) -> String {
    ans.len().to_string()
        + "\n"
        + &ans
            .into_iter()
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join(" ")
}
0