結果
問題 | 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^15 for(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; */ } }