結果
問題 | No.2071 Shift and OR |
ユーザー |
|
提出日時 | 2023-07-11 14:54:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,192 ms / 2,000 ms |
コード長 | 2,176 bytes |
コンパイル時間 | 1,131 ms |
コンパイル使用メモリ | 109,340 KB |
最終ジャッジ日時 | 2025-02-15 09:46:54 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include<iostream>#include<set>#include<algorithm>#include<vector>#include<string>#include<set>#include<map>#include<numeric>#include<queue>#include<cmath>using namespace std;typedef long long ll;const ll INF=1LL<<60;typedef pair<int,int> P;typedef pair<int,P> PP;const ll MOD=998244353;const double PI=acos(-1);void printbit(int n){if(n==0) cout<<"0"<<endl;vector<int> c;while(n>0){c.push_back(n%2);n/=2;}reverse(c.begin(),c.end());for(int v:c){cout<<v;}cout<<endl;}int shift(int x){return (((x%2)<<15) + (x/2));}int bithead(int x){int cnt=0;while(x>0){cnt++;x/=2;}return cnt;}int main(){int N;cin>>N;vector<int> A(N);for(int i=0;i<N;i++){cin>>A[i];}if(N>=15){//鳩ノ巣原理//A[i]のどれかはbit1が立っているので 1を15個連続して立たせることが可能int ans=(1<<16)-1;cout<<ans<<endl;}else{//N<15//全探索で処理int ans=0;map<P,int> memo;auto dfs=[&](auto f,int idx,int num)->int{if(memo.count(make_pair(idx,num))) return memo[make_pair(idx,num)];if(idx==N){//ans=max(ans,num);//return ans;return num;}int res=0;for(int c=0;c<15;c++){res=max(res,f(f,idx+1,num|A[idx]));A[idx]=shift(A[idx]);}return memo[make_pair(idx,num)]=res;};ans=dfs(dfs,0,0);cout<<ans<<endl;/*int ans=0;int c=15;//2^15for(int i=0;i<N;i++){cout<<"i="<<i<<endl;int n=A[i];while(( (n>>c)&1)==0){n=shift(n);//cout<<"n="<<n<<endl;}printbit(n);ans|=n;cout<<"ans="<<ans<<endl;printbit(ans);c--;}cout<<ans<<endl;*/}}