Submission #92397

#	Time	Username	Problem	Language	Result	Execution time	Memory
92397		KLPP	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	175 ms	632 KiB

sculpture

#include<iostream>

using namespace std;
typedef long long int lld;
lld ans[60];
lld DP1[20001];
int n,a,b;
lld arr[3000];
lld pow[60];
bool DP2[2000][2000];
void compute1(){
	lld sum[n+1];
	sum[0]=0;
	for(int i=0;i<n;i++){
		sum[i+1]=sum[i]+arr[i];
	}
	lld CMP=0;
	for(int i=0;i<60;i++)CMP+=(1-ans[i])*pow[i];
	//cout<<CMP<<endl;
	DP1[0]=0;
	for(int i=1;i<=n;i++){
		DP1[i]=100000;
		for(int j=0;j<i;j++){
			lld A=sum[i]-sum[j];
			//cout<<A<<endl;
			//cout<<(CMP&A)<<endl;
			if((CMP&A)==0){
				DP1[i]=min(DP1[i],DP1[j]+1);
			}
		}
		//cout<<DP1[i]<<" ";
	}
	//cout<<endl;
}
void compute2(){
	lld sum[n+1];
	sum[0]=0;
	for(int i=0;i<n;i++){
		sum[i+1]=sum[i]+arr[i];
	}
	lld CMP=0;
	for(int i=0;i<60;i++)CMP+=(1-ans[i])*pow[i];
	//cout<<CMP<<endl;
	
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++)DP2[i][j]=false;
	}DP2[0][0]=true;
	for(int i=1;i<=n;i++){
		for(int part=1;part<=n;part++){
		for(int j=0;j<i;j++){
			lld A=sum[i]-sum[j];
			//cout<<A<<endl;
			//cout<<(CMP&A)<<endl;
			if((CMP&A)==0){
				DP2[i][part]=DP2[i][part]|DP2[j][part-1];
			}
		}
		}
		//cout<<DP1[i]<<" ";
	}
}
int main(){
	cin>>n>>a>>b;
	for(int i=0;i<n;i++)cin>>arr[i];
	pow[0]=1;
	for(int i=0;i<59;i++)pow[i+1]=2*pow[i];
	if(a==1){
		for(int i=0;i<60;i++)ans[i]=1;
		for(int i=59;i>-1;i--){
			ans[i]=0;
			compute1();
			if(DP1[n]>b)ans[i]=1;
		}
		lld ANS=0;
		for(int i=0;i<60;i++)ANS+=ans[i]*pow[i];
		cout<<ANS<<endl;
		return 0;
	}
	for(int i=0;i<60;i++)ans[i]=1;
		for(int i=59;i>-1;i--){
			ans[i]=0;
			compute2();
			ans[i]=1;
			for(int p=a;p<=b;p++){
				if(DP2[n][p]){
					ans[i]=0;
				}
			}
		}
		lld ANS=0;
		for(int i=0;i<60;i++)ANS+=ans[i]*pow[i];
		cout<<ANS<<endl;

	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29