結果

問題 No.3502 GCD Knapsack
コンテスト
ユーザー magurofly
提出日時 2026-04-17 21:16:55
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 36 ms / 2,000 ms
コード長 596 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,351 ms
コンパイル使用メモリ 191,992 KB
実行使用メモリ 10,248 KB
最終ジャッジ日時 2026-04-17 21:17:13
合計ジャッジ時間 11,880 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]

fn main() {
  input! {
    N: usize, W: usize,
    X: [usize; N],
    Y: [i64; N],
  }

  let max = (*X.iter().max().unwrap()).max(W);
  
  let mut value = vec![0; max + 1];
  for i in 0 .. N {
    value[X[i]] += Y[i];
  }

  // dp[i] = i が約数になる value の和の最大
  let mut dp = vec![0; max + 1];
  for i in 1 ..= max {
    for j in (i ..= max).step_by(i) {
      dp[i] += value[j];
    }
  }

  let mut ans = 0;
  for i in W ..= max {
    ans = ans.max(dp[i]);
  }

  println!("{ans}");
}

use proconio::input;
0