제출 #1305718

#제출 시각아이디문제언어결과실행 시간메모리
1305718coolboy19521Bali Sculptures (APIO15_sculpture)C++20
100 / 100
81 ms580 KiB
#include "bits/stdc++.h"

#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;i>=(a);i--)
#define R0F(i,a)ROF(i,0,a)
#define REP(a)F0R(_,a)

using namespace std;

#define int long long

const int mxl=45;

signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n,a,b;cin>>n>>a>>b;
	vector<int>y(n+2);
	FOR(i,1,n+1)cin>>y[i];
	long long msk=(1ll<<mxl)-1;
	if(a==1)R0F(i,mxl){
		vector<int>dp(n+1,n+1);
		dp[0]=0,msk^=1ll<<i;
		for(int j=1,s=y[j];j<=n;s=y[++j])
			for(int k=j;k>=1;s+=y[--k])
				if(dp[k-1]<b and (s&msk)==s)dp[j]=min(dp[j],dp[k-1]+1);
		if(dp[n]>b)msk^=1ll<<i;
	}else R0F(i,mxl){
		vector<vector<bool>>dp(n+1,vector<bool>(n+1,false));
		dp[0][0]=true,msk^=1ll<<i;
		for(int j=1,s=y[j];j<=n;s=y[++j])
			for(int k=j;k>=1;s+=y[--k])FOR(l,1,k+1)
				dp[j][l]=dp[j][l] or (dp[k-1][l-1] and (s&msk)==s);
		bool f=false;FOR(j,a,b+1)f|=dp[n][j];
		if(not f)msk^=1ll<<i;
	}
	cout<<msk<<'\n';
}
#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...