結果
問題 |
No.3041 非対称じゃんけん
|
ユーザー |
|
提出日時 | 2025-03-01 20:10:25 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,014 bytes |
コンパイル時間 | 12,606 ms |
コンパイル使用メモリ | 397,628 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-03-01 20:10:52 |
合計ジャッジ時間 | 27,298 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 6 WA * 21 TLE * 3 |
ソースコード
// use std::num::Wrapping; fn main() { input!{ n: usize, _f: usize, a: [u64; n], b: [u64; n], c: [u64; n], } // abcをまとめる let mut abc = vec![vec![0; 3]; n]; for i in 0..n { abc[i][0] = a[i]; abc[i][1] = b[i]; abc[i][2] = c[i]; } // dp状態のサイズ(論理和なので1つの要素につき、maxはn) let sz_max = n; // dp[i番目まで見た][指の合計本数j(bitで表現)] = true/false let mut cur_dp = vec![0u64; sz_max+2]; let mut next_dp = cur_dp.clone(); cur_dp[0] = 1; let mut ans = Vec::new(); // もらうDP for i in 0..n { for k in 0..3 { // 遷移しないものを受け取る if abc[i][k] == 0 { for next in 0..=sz_max { next_dp[next] |= cur_dp[next]; } } // 遷移するものを受け取る else { for next in 0..=sz_max { // 最下位桁のみ、同じ桁からしか取れない if next == 0 { next_dp[next] |= cur_dp[next].wrapping_shl(abc[i][k] as u32); } else { next_dp[next] |= cur_dp[next].wrapping_shl(abc[i][k] as u32) | (cur_dp[next-1] >> ((64 - abc[i][k]) as u32)); } } } } // 状態毎のbitが立っている数を数える let mut ret = 0; for i in 0..=sz_max { ret += next_dp[i].count_ones(); } ans.push(ret); // cur,nextを交換 swap(&mut cur_dp, &mut next_dp); } // 出力 for i in ans { print!("{}\n", i); } } // const MOD17: usize = 1000000007; // const MOD93: usize = 998244353; // const INF: usize = 1 << 60; // let dx = vec![!0, 0, 1, 0]; // 上左下右 // let dy = vec![0, !0, 0, 1]; // 上左下右 // let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; // 上左下右 // use itertools::Itertools; #[allow(unused)] use proconio::{input, marker::Chars, marker::Usize1}; #[allow(unused)] use std::{ mem::swap, cmp::min, cmp::max, cmp::Reverse, collections::HashSet, collections::BTreeSet, collections::HashMap, collections::BTreeMap, collections::BinaryHeap, collections::VecDeque, iter::FromIterator, };