結果
問題 | No.2410 Nine Numbers |
ユーザー |
|
提出日時 | 2023-08-12 01:03:22 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 1,515 bytes |
コンパイル時間 | 12,905 ms |
コンパイル使用メモリ | 382,256 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-18 20:49:05 |
合計ジャッジ時間 | 13,912 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 |
ソースコード
#![allow(dead_code)]#![allow(unused_imports)]#![allow(non_snake_case)]#![allow(unused_variables)]const UINF: usize = std::usize::MAX;const IINF: isize = std::isize::MAX;const UMOD: usize = 998244353;//const UMOD: usize = 1000000007;const IMOD: isize = 998244353;//const IMOD: isize = 1000000007;fn yn(flag: bool) {if flag { println!("Yes") }else { println!("No") }}fn YN(flag: bool) {if flag { println!("YES") }else { println!("NO") }}fn print_vec<T: std::fmt::Display>(a: &Vec<T>, sep: &str) {if a.is_empty() { println!("") }else {let dst: Vec<String> = a.iter().map(|x| x.to_string()).collect();println!("{}", dst.join(sep));}}fn solve(s: usize) {let mut dp = vec![vec![false; 9001]; 9];dp[0][0] = true;let mut ans = Vec::new();ans.push(s);dp[0][s] = true;while ans.len() < 9 {let i = ans.len();let last = *ans.last().unwrap();let mut a = 0;for j in 0..=9000 {if !dp[i-1][j] {a = 2 * j - 1;break;}}ans.push(a);for j in 0..=9000 {if j >= a {dp[i][j-a] |= dp[i-1][j];} else if a - j <= 9000 {dp[i][a-j] |= dp[i-1][j];}dp[i][j] |= dp[i-1][j];if j + a <= 9000 {dp[i][j+a] |= dp[i-1][j];}}}print_vec(&ans, " ");}fn main () {solve(1);}