Codeforces Round #320 (Div. 1) [Bayan Thanks-Round]

B."Or" Game

$\mathtt{Difficulty}$=$\mathtt{1700}$
不难发现，将 $x^k$ 乘在同一个数上一定最优。
首先我们有 $\mathcal{O(n^2)}$ 的暴力算法。
于是我们考虑如何优化。
因为每次变化的只有一个数 $a_i$，
所以我们不妨记录前缀或和后缀或，
然后枚举 $i$ 计算 $a_i\times x^k$ 即可得到答案。
即：Ans=max(Ans,(A[i]*Ret)|Pre[i-1]|Nxt[i+1])

#include<bits/stdc++.h>
using namespace std;
#define int long long
int N,K,X,A[200001],Pre[200001],Nxt[200001];
signed main(void)
{
	register int i;cin>>N>>K>>X;
	for(i=1;i<=N;i++)cin>>A[i];
	register int Ret=1;
	while(K--)Ret*=X;
	for(i=1;i<=N;i++)Pre[i]=Pre[i-1]|A[i];
	for(i=N;i>=1;i--)Nxt[i]=Nxt[i+1]|A[i];
	register int Ans=0;
	for(i=1;i<=N;i++)Ans=max(Ans,(A[i]*Ret)|Pre[i-1]|Nxt[i+1]);
	cout<<Ans<<endl;
	return 0;
}