結果
問題 | No.2071 Shift and OR |
ユーザー |
|
提出日時 | 2024-08-15 22:01:02 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 833 bytes |
コンパイル時間 | 13,419 ms |
コンパイル使用メモリ | 400,564 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-15 22:01:18 |
合計ジャッジ時間 | 13,788 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
use proconio::input;fn main() {input! {n:usize,a:[usize;n],}const D: usize = 16;if n >= D {let ans = (1 << 16) - 1;println!("{}", ans);return;}let mut dp = vec![vec![false; 1 << D]; n + 1];dp[0][0] = true;for i in 0..n {for j in 0..1 << D {if !dp[i][j] {continue;}let mut x = a[i];for _ in 0..D {dp[i + 1][j | x] = true;x = shift(x);}}}for i in (0..1 << D).rev() {if dp[n][i] {let ans = i;println!("{}", ans);return;}}}fn shift(x: usize) -> usize {if x & 1 == 0 {x >> 1} else {(x >> 1) | (1 << 15)}}