結果
問題 |
No.3041 非対称じゃんけん
|
ユーザー |
|
提出日時 | 2025-03-01 19:15:04 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,805 bytes |
コンパイル時間 | 12,670 ms |
コンパイル使用メモリ | 391,048 KB |
実行使用メモリ | 8,236 KB |
最終ジャッジ日時 | 2025-03-01 19:15:34 |
合計ジャッジ時間 | 29,522 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 WA * 18 TLE * 5 |
ソースコード
use std::num::Wrapping; fn main() { input!{ n: usize, _f: usize, a: [usize; n], b: [usize; n], c: [usize; 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![0usize; sz_max+2]; cur_dp[0] = 1; // くばるDP for i in 0..n { let mut next_dp = vec![0usize; sz_max+2]; for cur in 0..=sz_max { for k in 0..3 { // 繰り上がりあり if abc[i][k] > 0 && (cur_dp[cur] & (1 << (64 - abc[i][k]))) != 0 { let mut upper_state = Wrapping(cur_dp[cur]); upper_state >>= 64 - abc[i][k]; next_dp[cur+1] |= upper_state.0; } // 繰り上がりなし let mut lower_state = Wrapping(cur_dp[cur]); lower_state <<= abc[i][k]; next_dp[cur] |= lower_state.0; } } // 状態毎の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, };