记录编号	402557	评测结果	AAAAAAAAAA
题目名称	[APIO2015]巴厘岛的雕塑	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.276 s
提交时间	2017-05-06 19:55:35	内存使用	4.16 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=2010;
int n,l,r;
ll sum[N],ans=(1ll<<41)-1;
void solve1(){
	static bool dp[N][N];
	//dp[i][j][k]表示用到了第i个,分了j段,不含当前位的合法性 
	for (ll x=1ll<<40;x;x>>=1){
		for (int i=0;i<=n;i++)
		for (int j=0;j<=n;j++)
			dp[i][j]=0;
		dp[0][0]=1;
		ans^=x;
		for (int i=0;i<n;i++)
		for (int j=0;j<=i;j++)
		if (dp[i][j]){
			for (int k=i+1;k<=n;k++){
				ll S=sum[k]-sum[i];
				if ((S&ans)==S) dp[k][j+1]=1;
			}
		}
		for (int i=l;i<=r;i++)
			if (dp[n][i]) goto nxt;
		ans^=x;
		nxt:;
	}
	printf("%lld\n",ans);
}
void solve2(){
	static int dp[N];
	//dp[i]为用到第i位且不含当前位所分的最少段数 
	for (ll x=1ll<<40;x;x>>=1){
		for (int i=0;i<=n;i++) dp[i]=1e9;
		dp[0]=0;
		ans^=x;
		for (int i=0;i<n;i++)
		if (dp[i]<1e9){
			for (int k=i+1;k<=n;k++){
				ll S=sum[k]-sum[i];
				if ((S&ans)==S) dp[k]=min(dp[k],dp[i]+1);
			}
		}
		if (dp[n]>r) ans^=x;
	}
	printf("%lld\n",ans);
}
int main()
{
	freopen("sculpture.in","r",stdin);
	freopen("sculpture.out","w",stdout);
	scanf("%d%d%d",&n,&l,&r);
	for (int i=1;i<=n;i++) scanf("%lld",&sum[i]),sum[i]+=sum[i-1];
	if (n<=100) solve1();else solve2();
	return 0;
}