結果
問題 |
No.3041 非対称じゃんけん
|
ユーザー |
|
提出日時 | 2025-03-01 19:30:29 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,821 bytes |
コンパイル時間 | 12,920 ms |
コンパイル使用メモリ | 406,528 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-03-01 19:30:59 |
合計ジャッジ時間 | 30,004 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 TLE * 5 |
ソースコード
// 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]; cur_dp[0] = 1; // もらうDP for i in 0..n { let mut next_dp = vec![0u64; sz_max+2]; for next in 0..=sz_max { for k in 0..3 { // 遷移しないものを受け取る if abc[i][k] == 0 { next_dp[next] |= cur_dp[next]; } // 遷移するものを受け取る else { 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 ans = 0; for i in 0..=sz_max { ans += next_dp[i].count_ones(); } println!("{}", ans); // cur,nextを交換 swap(&mut cur_dp, &mut next_dp); } } // 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)}; // 上左下右 #[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, };