結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー elphe
提出日時 2025-10-25 12:04:32
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 57 ms / 1,571 ms
コード長 1,040 bytes
コンパイル時間 12,952 ms
コンパイル使用メモリ 398,184 KB
実行使用メモリ 37,376 KB
最終ジャッジ日時 2025-11-02 16:31:43
合計ジャッジ時間 15,961 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 74
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `N` should have a snake case name
 --> src/main.rs:7:9
  |
7 |         N: usize,
  |         ^ help: convert the identifier to snake case: `n`
  |
  = note: `#[warn(non_snake_case)]` on by default

warning: variable `W` should have a snake case name
 --> src/main.rs:8:9
  |
8 |         W: usize,
  |         ^ help: convert the identifier to snake case (notice the capitalization): `w`

warning: variable `N` should have a snake case name
  --> src/main.rs:24:10
   |
24 | fn solve(N: usize, W: usize, v: &[u32], w: &[usize]) -> Vec<u32> {
   |          ^ help: convert the identifier to snake case: `n`

warning: variable `W` should have a snake case name
  --> src/main.rs:24:20
   |
24 | fn solve(N: usize, W: usize, v: &[u32], w: &[usize]) -> Vec<u32> {
   |                    ^ help: convert the identifier to snake case (notice the capitalization): `w`

ソースコード

diff #
raw source code 

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::<Vec<_>>().join(" ");
        println!("{}", s);
    } else {
        println!();
    }
}

fn solve(N: usize, W: usize, v: &[u32], w: &[usize]) -> Vec<u32> {
    let mut dp: Vec<Vec<u32>> = 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<u32> = 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
}
0