Submission #15813

#	Time	Username	Problem	Language	Result	Execution time	Memory
15813		jihoon	Bali Sculptures (APIO15_sculpture)	C++98	100 / 100	151 ms	1112 KiB

sculpture

#include<cstdio>
long long int sum[2002];
int dp[2002][2];
int main(){
	long long int dap,gap=1,im,ddd;
	int n,a,b,c1,c2;
	for(int i=1;i<=41;i++){
		gap*=2;
	}
	scanf("%d%d%d",&n,&a,&b);
	sum[0]=0;
	for(int i=1;i<=n;i++){
		scanf("%lld",&im);
		sum[i]=sum[i-1]+im;
	}
	dap=gap;
	ddd=gap;
	dp[0][0]=0;
	dp[0][1]=0;
	while(gap>0){
		for(int i=1;i<=n;i++){
			dp[i][0]=n+2;dp[i][1]=-1;
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<i;j++){
				if(dp[j][1]==-1) continue;
				im=sum[i]-sum[j];
				if(im<=dap&&((im & ddd)==0)){
					if(dp[i][0]>dp[j][0]+1) dp[i][0]=dp[j][0]+1;
					if(dp[i][1]<dp[j][1]+1) dp[i][1]=dp[j][1]+1; 
				}
			}
		}
		c1=a;c2=b;
		if(c1<dp[n][0]) c1=dp[n][0];
		if(c2>dp[n][1]) c2=dp[n][1];
		gap/=2;
		ddd+=gap;
		if(a<=c1&&c1<=c2&&c2<=b){
			dap-=gap;
			if(gap==0) dap--;
		}else{
			ddd-=(gap*2);
			dap+=gap;
		}
	}
	printf("%lld",dap);
}

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