Cf. bits and pieces (subset pressing DP + pruning)

Ideas ：

Greedily consider from high to low , For arbitrary i, If a[i] Of the x Is it 1, Then don't worry ; If the first x Is it 0, Then I hope I can find it a[j] and a[k] Satisfy i<j<k, also a[j] & a[k] = 1.

Then we can traverse in reverse order i, For all the  j  [i+1, n], We put a[j] The number of occurrences of the subset of is recorded in A In array , such as [i+1,n] Within the scope of a[j] by 10,11,100（ All written in binary ）, that A[10] = 2, Because two numbers have subsets 10.

that , When does it exist a[j] and a[k] Satisfy i<j<k, also a[j] & a[k] = 1 Well ？ Namely A[mask] >= 2 When , among mask It contains a[i] All that need to be supplemented at present 1.

If you don't understand , Please look at the code. ：

code1（tle）：

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define debug cout<<111<<endl;
const int N = 1e6+5;
int n, a[N], f[(1<<20)+5], ans=0;

void add(int x,int p){
    if(p==-1) {f[x]++; return;} // All bits are traversed , The number of schemes in this subset +1
    add(x,p-1); // Keep the original sample , Down add
    if(x&(1<<p)) add(x^(1<<p), p-1); // The first p Bit handle 1 Change to 0, Down add
}
inline void solve(){
    cin>>n; FOR(i,1,n) cin>>a[i];
    add(a[n],20); add(a[n-1],20);
    for(int i=n-2; i>=1; i--){
        int mask=0;
        for(int j=20; j>=0; j--){
            if(a[i] & (1<<j)) continue; // If a[i] This is originally 1, Then don't worry about 
            if(f[mask|(1<<j)] >= 2) mask |= (1<<j); // Greedy j position 
        }
        ans = max(ans, a[i]|mask);
        add(a[i],20); // hold a[i] Also join the right f In the contribution of 
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T=1; while(T--) solve();
}

Ran goose , This code tle 了 .

Why? ？ Because the parameters are exactly the same add It may be done many times , But the same add After more than two times, it will not affect A[mask] >= 2 了 , So it can be used f[i][j] Record add(i,j) The number of iterations  , Traversed more than twice directly return fall , Finish pruning .

This is after pruning ac Code ：

code2（ac）：

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define debug cout<<111<<endl;
const int N = 1e6+5;
int n, a[N], A[N*2], ans=0;
int f[N*2][22];

void add(int x,int p){
    if(p==-1) {A[x]++; return;} // All bits are traversed , The number of schemes in this subset +1
    if(f[x][p]>=2) return; // This add It has been traversed twice , All corresponding A[y]（y yes x Subset ） At least also 2 了 , So prune off 
    f[x][p]++; // I went through it once add(x,p), recorded 
    add(x,p-1); // Keep the original sample , Down add
    if(x&(1<<p)) add(x^(1<<p), p-1); // The first p Bit handle 1 Change to 0, Down add
}
inline void solve(){
    cin>>n; FOR(i,1,n) cin>>a[i];
    add(a[n],20); add(a[n-1],20);
    for(int i=n-2; i>=1; i--){
        int mask=0;
        for(int j=20; j>=0; j--){
            if(a[i] & (1<<j)) continue; // If a[i] This is originally 1, Then don't worry about 
            if(A[mask|(1<<j)] >= 2) mask |= (1<<j); // Greedy j position 
        }
        ans = max(ans, a[i]|mask);
        add(a[i],20); // hold a[i] Also join the right f In the contribution of 
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T=1; while(T--) solve();
}