結果

問題 No.2866 yuusaan's Knapsack
ユーザー magurofly
提出日時 2024-08-30 22:41:44
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 2,436 bytes
コンパイル時間 12,340 ms
コンパイル使用メモリ 388,840 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-26 14:37:29
合計ジャッジ時間 13,548 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `N` should have a snake case name
 --> src/main.rs:8:9
  |
8 |         N: usize, W: i64,
  |         ^ 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:19
  |
8 |         N: usize, W: i64,
  |                   ^ help: convert the identifier to snake case (notice the capitalization): `w`

ソースコード

diff # 

use proconio::input;

const INF: i64 = 1_000_000_000_000_000_000;
const MOD: i64 = 998244353;

fn main() {
    input! {
        N: usize, W: i64,
        mut items: [(i64, i64); N],
    }
    items.sort_by_key(|p| p.1 );

    let mut dp = vec![(-INF, 0i64, false); 30000 as usize];
    dp[10000] = (0, 1, true);

    for (v, w) in items {
        if w > 0 {
            for w_sum in (0 .. dp.len() as i64).rev() {
                if (0 .. dp.len() as i64).contains(&(w_sum + w)) {
                    let (v_sum, count, exist) = dp[w_sum as usize];
                    if !exist {
                        continue;
                    }
                    let v_sum_next = v_sum + v;
                    let w_sum_next = (w_sum + w) as usize;
                    if dp[w_sum_next].0 < v_sum_next {
                        dp[w_sum_next] = (v_sum_next, count, true);
                    } else if dp[w_sum_next].0 == v_sum_next {
                        dp[w_sum_next].1 += count;
                        dp[w_sum_next].1 %= MOD;
                        dp[w_sum_next].2 = true;
                    }
                }
            }
        } else if w < 0 {
            for w_sum in 0 .. dp.len() as i64 {
                if (0 .. dp.len() as i64).contains(&(w_sum + w)) {
                    let (v_sum, count, exist) = dp[w_sum as usize];
                    if !exist {
                        continue;
                    }
                    let v_sum_next = v_sum + v;
                    let w_sum_next = (w_sum + w) as usize;
                    if dp[w_sum_next].0 < v_sum_next {
                        dp[w_sum_next] = (v_sum_next, count, exist);
                    } else if dp[w_sum_next].0 == v_sum_next {
                        dp[w_sum_next].1 += count;
                        dp[w_sum_next].1 %= MOD;
                        dp[w_sum_next].2 = true;
                    }
                }
            }
        } else if v > 0 {
            for x in &mut dp {
                x.0 += v;
            }
        }
    }

    let mut value_max = -INF;
    let mut count = 0;
    for i in 0 ..= (10000 + W) as usize {
        let (v, c, x) = dp[i];
        if x {
            if value_max < v {
                value_max = v;
                count = c;
            } else if value_max == v {
                count += c;
                count %= MOD;
            }
        }
    }
    println!("{value_max} {count}");
}
0