原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ110.html
题解
我们发现n=2000 的子任务保证A=1！
分两种情况讨论：
$n\leq 100$：
贪心地从高位到低位逐位考虑，看当前位是否可以放 0。用 $dp[i][j]$ 表示前 $i$ 个数是否可以在各段sum的or值不超过当前上限的情况下分成 $j$ 段。
时间复杂度 $O(n^3 \log V)$ 。
$A = 1$：
贪心地从高位到低位逐位考虑，看当前位置是否可以放0。 用 $dp[i][0/1]$ 表示前 $i$ 个数，在各段sum的or值不超过当前上限的情况下，当前位的or值是 $0/1$ 的情况下最少分成几段。
时间复杂度 $O(n^2 \log V)$ 。
代码
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
using namespace std;
typedef long long LL;
LL read(){
LL x=0,f=0;
char ch=getchar();
while (!isdigit(ch))
f|=ch=='-',ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
const int N=2005;
int n,A,B;
LL a[N];
void ckMin(int &x,int y){
x=x<y?x:y;
}
namespace so1{
const int N=105;
int dp[N][N];
int check(LL v){
clr(dp);
dp[0][0]=1;
for (int i=1;i<=n;i++)
for (int j=0;j<i;j++)
if ((v|(a[i]-a[j]))==v)
for (int k=0;k<n;k++)
dp[i][k+1]|=dp[j][k];
for (int i=1;i<=n;i++)
if (A<=i&&i<=B&&dp[n][i])
return 1;
return 0;
}
void main(){
LL ans=0;
for (int i=40;i>=0;i--)
if (!check(ans|((1LL<<i)-1)))
ans|=1LL<<i;
cout<<ans<<endl;
}
}
namespace so2{
const int N=2005;
int dp[N][2];
void main(){
LL ans=0;
for (int d=40;d>=0;d--){
for (int i=0;i<N;i++)
dp[i][0]=dp[i][1]=1e9;
dp[0][0]=0;
LL v=ans|((1LL<<(d+1))-1);
for (int i=1;i<=n;i++)
for (int j=0;j<i;j++)
if ((v|(a[i]-a[j]))==v)
for (int t=0;t<2;t++)
ckMin(dp[i][t|((a[i]-a[j])>>d&1LL)],dp[j][t]+1);
if (dp[n][0]>B)
ans|=1LL<<d;
}
cout<<ans<<endl;
}
}
int main(){
n=read(),A=read(),B=read();
for (int i=1;i<=n;i++)
a[i]=a[i-1]+read();
if (n<=100)
so1::main();
else
so2::main();
return 0;
}