codeforces#320(div2) D Or Game 贪心

2023-09-09 阅读 19 评论 0

摘要：codeforces#320(div2) D "Or" Game 贪心 D. "Or" Game time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output You are givennnumbersa1, a2, ..., an. You can perform at mostkoperations. F

codeforces#320(div2) D "Or" Game 贪心

You are given n numbers a1, a2, ..., an. You can perform at most k operations. For each operation you can multiply one of the numbers by x. We want to make $\text{[math]}$ as large as possible, where $\text{[math]}$ denotes the bitwise OR.

Find the maximum possible value of $\text{[math]}$ after performing at most k operations optimally.

Input

The first line contains three integers n, k and x (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 10, 2 ≤ x ≤ 8).

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109).

Output

Output the maximum value of a bitwise OR of sequence elements after performing operations.

Sample test(s)

input

3 1 2
1 1 1

output

input

4 2 3
1 2 4 8

output

Note

For the first sample, any possible choice of doing one operation will result the same three numbers 1, 1, 2 so the result is $\text{[math]}$ .

For the second sample if we multiply 8 by 3 two times we'll get 72. In this case the numbers will become 1, 2, 4, 72 so the OR value will be 79 and is the largest possible result.

一开始看错题了。。。。后来随便脑补了一下，干脆直接把所有的数扔在一个数上。比赛的时候手误打错了一个字符，把a打成了s，居然也能过。。。。。。。最后自然是FST了，，，，本来分可以涨的更多。。。。。在codeforces打错一个字符最多只是FST一道题，再严重也不过掉rating而已，下次可以打回来，如果是网络赛出现这种情况不仅会WA一次罚时20min，而且要花更多的时间调试，很可能卡题，影响全队的状态，所以写代码一定要处处小心，在正确的前提下再保证手速。

如果这题没想到可以把其它的值的取或的值存起来的方法的时候怎么办呢，可以建一颗线段树，单点修改，总区间求和(取或)，数据结构真是万能的东西，学得越深越觉得它弥补了自己思维的不足。

虽然这题FST了，但是还是涨到蓝了，学了这么久，终于摆脱绿名了，而且是在B题水题没做，D题仅仅因打错一个字符FST的情况下，涨到蓝了。

虽然涨分了，但是还是要补E题的三分，还是要尽快学splay，学LCT。

#include<bits/stdc++.h>using namespace std;typedef long long ll;
const ll INF=(1LL<<60);
const double EPS=0.00000000000001;
const int maxn=2000100;ll n,k,x;
ll a[maxn];
ll b[maxn];
ll s[maxn],fs[maxn];ll qpow(ll n,ll k)
{ll res=1;while(k){if(k&1) res*=n;n*=n;k>>=1;}return res;
}int main()
{while(cin>>n>>k>>x){for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);ll mul=qpow(x,k);memset(s,0,sizeof(s));memset(fs,0,sizeof(fs));for(int i=1;i<=n;i++){s[i]=s[i-1]|a[i];}for(int i=n;i>=1;i--){fs[i]=fs[i+1]|a[i];}for(int i=1;i<=n;i++){b[i]=s[i-1]|fs[i+1];}ll tmp=0,ans=0;for(int i=1;i<=n;i++){ll t=a[i];a[i]*=mul;tmp=a[i]|b[i];ans=max(tmp,ans);a[i]=t;}cout<<ans<<endl;}return 0;
}