我们一位一位地来做,每次判断这一位能否放0,而且要在满足前几位的情况下。用dp来判断
具体来说,设f[i][j]表示前i个划分成j个区间能否满足,那么我们会有转移trans[i][k+1],当区间[i,k]的和在某些位上不是1时trans[i][k+1]=1
这些位,就是正在做的这位和它之前确定下来的取0的位数
那么每次就看f[N+1][A...B]是否有值,就可以确定下来这位答案到底是放0还是1了
这样做的复杂度,是O(n^3logV)的,最后一个子任务过不去
发现最后一个子任务A=1,那我们就可以在dp时少记一维,令f[i]表示使前i个数满足的最小区间数,看最后f{N+1]能否<=B就可以了
(或者像我一样zz地写一个最短路)
有一个要注意的点,就是<<操作,如果超出范围,是要写成类似于1LL<<55这样的
#include<bits/stdc++.h>
#define pa pair<int,int>
#define ll long long
using namespace std;
const int maxm=,maxn=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,M,A,B,dis[maxn];
bool tmp[maxn][maxn];
bool trans[maxn][maxn],f[maxn][maxn],flag[maxn];
ll sum[maxn],num[maxn];
priority_queue<pa,vector<pa>,greater<pa> > q; inline bool dp(){
memset(f,,sizeof(f));f[][]=;
for(int i=;i<B;i++){
for(int j=;j<=N;j++){if(!f[i][j]) continue;
for(int k=j+;k<=N+;k++){
if(!trans[j][k]) continue;
f[i+][k]=;
}
}
}bool can=;
for(int i=A;i<=B;i++){
can|=f[i][N+];
}return can;
}
inline bool dijkstra(){
memset(dis,,sizeof(dis));while(!q.empty()) q.pop();
memset(flag,,sizeof(flag));
dis[]=;q.push(make_pair(,));
while(!q.empty()){
int p=q.top().second;q.pop();if(flag[p]) continue;
if(p==N+) break;
for(int i=p+;i<=N+;i++){
if(!trans[p][i]||dis[i]<=dis[p]+) continue;
dis[i]=dis[p]+;q.push(make_pair(dis[i],i));
}
}return dis[N+]<=B;
} inline void solve(){
ll ans=;int i,j,k;
for(i=;i<=N;i++) sum[i]=sum[i-]+num[i];
ll l=sum[N];while(l) M++,l>>=;
memset(trans,,sizeof(trans));
for(int t=M;t;t--){
memcpy(tmp,trans,sizeof(tmp));
for(int i=;i<=N;i++){
for(int j=i;j<=N;j++){
if((sum[j]-sum[i-])&(1LL<<(t-))) trans[i][j+]=;
}
}
bool can=(A==)?dijkstra():dp();
if(!can){
ans|=1LL<<(t-);memcpy(trans,tmp,sizeof(tmp));
}
}
printf("%lld\n",ans);
} int main(){
int i,j,k;
//freopen("1967.in","r",stdin);
N=rd(),A=rd(),B=rd();
for(i=;i<=N;i++) num[i]=rd();
solve();
return ;
}