結果
問題 | No.2071 Shift and OR |
ユーザー |
![]() |
提出日時 | 2022-09-16 21:41:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 1,019 bytes |
コンパイル時間 | 2,090 ms |
コンパイル使用メモリ | 200,016 KB |
最終ジャッジ日時 | 2025-02-07 09:12:04 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h>using namespace std;int64_t shift(int64_t x) { return x / 2 + (1ull << 15) * (x % 2); }int main() {int64_t N;cin >> N;vector<int64_t> A(N);for (int64_t& a : A) {cin >> a;}const int64_t M = 16;const int64_t max_bit = (1ull << M);vector<bool> can_make(max_bit, false);can_make[0] = true;for (int64_t i = 0; i < N; i++) {vector<bool> new_can_make = can_make;for (int64_t k = 0; k < M; k++) {for (int64_t j = 0; j < max_bit; j++) {const int64_t nj = (j | A[i]);new_can_make[nj] = (new_can_make[nj] || can_make[j]);}A[i] = shift(A[i]);}can_make = new_can_make;if (can_make[max_bit - 1]) {cout << max_bit - 1 << endl;return 0;}}for (int64_t i = max_bit - 1; i >= 0; i--) {if (can_make[i]) {cout << i << endl;return 0;}}}