結果
問題 | No.2071 Shift and OR |
ユーザー |
![]() |
提出日時 | 2024-01-30 00:50:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 1,036 bytes |
コンパイル時間 | 1,870 ms |
コンパイル使用メモリ | 199,152 KB |
最終ジャッジ日時 | 2025-02-19 00:44:19 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<ll, ll>; #define rep(i, a, b) for(ll i = a; i < b; ++i) #define rrep(i, a, b) for(ll i = a; i >= b; --i) constexpr ll inf = 4e18; struct SetupIO { SetupIO() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(30); } } setup_io; int main(void) { int n; cin >> n; if(n >= 16) { cout << (1 << 16) - 1 << '\n'; return 0; } vector<int> a(n); rep(i, 0, n) { cin >> a[i]; } vector<vector<bool>> dp(n + 1, vector<bool>(1 << 16, false)); dp[0][0] = true; rep(i, 0, n) { rep(j, 0, 1 << 16) { rep(k, 0, 16) { dp[i + 1][j] = dp[i + 1][j] | dp[i][j]; dp[i + 1][j | a[i]] = dp[i + 1][j | a[i]] | dp[i][j]; a[i] = (a[i] >> 1) + (1 << 15) * (a[i] & 1); } } } int ans = 0; rep(i, 0, 1 << 16) { if(dp[n][i]) ans = i; } cout << ans << '\n'; }