Submission #251345

#TimeUsernameProblemLanguageResultExecution timeMemory
251345defineBali Sculptures (APIO15_sculpture)C++17
100 / 100
147 ms4352 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 998244353;
constexpr int inf = 3e18;

int N,A,B;
int Y[2005];
bool dp[2005][2005];
int dp2[2005];
void solve1(){
	int anti=0;
	rev(i,40){
		anti+=1ll<<i;
		memset(dp,0,sizeof(dp));
		dp[0][0]=true;
		rep(j,N){
			rep(k,B){
				if(!dp[j][k])continue;
				int sum=0;
				for(int l=j;l<N;l++){
					sum+=Y[l];
					if((sum&anti)==0)dp[l+1][k+1]=true;
				}
			}
		}
		bool flag=false;
		for(int j=A;j<=B;j++)flag|=dp[N][j];
		if(!flag)anti^=1ll<<i;
	}
	cout<<(anti^((1ll<<40)-1))<<endl;
}
void solve2(){
	int anti=0;
	rev(i,50){
		anti+=1ll<<i;
		fill(dp2,dp2+N+1,inf);
		dp2[0]=0;
		rep(j,N){
			int sum=0;
			for(int k=j;k<N;k++){
				sum+=Y[k];
				if((anti&sum)==0)chmin(dp2[k+1],dp2[j]+1);
			}
		}
		if(dp2[N]>B)anti^=1ll<<i;
	}
	cout<<(anti^((1ll<<50)-1))<<endl;
}
signed main(){
	cin>>N>>A>>B;
	rep(i,N)cin>>Y[i];
	if(N<=100)solve1();
	else solve2();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...