제출 #45202

#제출 시각아이디문제언어결과실행 시간메모리
45202ckodserBali Sculptures (APIO15_sculpture)C++14
100 / 100
234 ms968 KiB
#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=2100;
const ll mod=1e9+7;
const ll inf=1e18+500;

ll a[maxn];
ll n,A,B;



ll dpa1[maxn];
bool shoda1(ll res){
	dpa1[0]=0;
	for(ll i=1;i<=n;i++){
		dpa1[i]=inf;
		ll sum=0;
		for(ll j=i;j>=1;j--){
			sum+=a[j];
			if((sum|res)==res){
				dpa1[i]=min(dpa1[i],dpa1[j-1]+1);
			}
		}
	}
	if(dpa1[n]<=B){
		return 1;
	}
	return 0;
}
bool dp[maxn][maxn];
bool shod(ll res){
	dp[0][0]=1;
	for(ll i=1;i<=n;i++){
		for(ll z=1;z<=n;z++){
			dp[i][z]=0;
			ll sum=0;
			for(ll j=i;j>=1;j--){
				sum+=a[j];
				if((sum|res)==res){
					dp[i][z]|=dp[j-1][z-1];
				}
			}
		}
	}
	for(ll i=A;i<=B;i++){
		if(dp[n][i]){
			return 1;
		}
	}
	return 0;
}
int main(){	
	cin>>n>>A>>B;

	for(ll i=1;i<=n;i++){
		cin>>a[i];
	}
	if(A==1){
		ll res=0;
		for(ll i=60;i>=0;i--){
			if(!shoda1(res+(1LL<<i)-1)){
				res+=(1LL<<i);	
			}	
		}
		cout<<res<<endl;
	}
	else{
		ll res=0;
		for(ll i=60;i>=0;i--){
			if(!shod(res+(1LL<<i)-1)){
				res+=(1LL<<i);	
			}	
		}
		cout<<res<<endl;
	}
}
#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...