Submission #17336

#	Time	Username	Problem	Language	Result	Execution time	Memory
17336		comet	Bali Sculptures (APIO15_sculpture)	C++98	37 / 100	12 ms	22660 KiB

sculpture

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int a[2010];
int sum[2010];

int N,A,B;
int lim;

bool d[101][101][101];
int d2[2001][2001];
bool chk[101][101][101];
bool chk2[2001][2001];

int f(int x,int p){
	if(x>N){
		if(p==N)return 0;
		return 1e9;
	}
	int& ret=d2[x][p];
	if(chk2[x][p])return ret;
	ret=f(x+1,p);
	chk2[x][p]=1;
	if(((sum[x]-sum[p])|lim)==lim){
		ret=min(ret,f(x+1,x)+1);
	}
	return ret;
}

bool f(int x,int p,int cnt){
	if(x>N)return p==N&&cnt>A&&cnt<=B+1;
	if(cnt>B)return 0;

	bool& ret=d[x][p][cnt];
	if(chk[x][p][cnt])return ret;
	ret=0;
	chk[x][p][cnt]=1;
	if(((sum[x]-sum[p])|lim)==lim){
		ret|=f(x+1,x,cnt+1);
	}
	ret|=f(x+1,p,cnt);
	return ret;
}

int main(){
	scanf("%d%d%d",&N,&A,&B);
	for(int i=1;i<=N;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}

	if(A==1){
		lim=(1<<30)-1;
		for(int i=29;i>=0;i--){
			memset(chk2,0,sizeof(chk2));
			lim^=(1<<i);
			if(f(1,0)>B){
				lim^=(1<<i);
			}
		}
	}else{
		lim=(1<<30)-1;
		for(int i=29;i>=0;i--){
			memset(chk,0,sizeof(chk));
			lim^=(1<<i);
			if(!f(1,0,1)){
				lim^=(1<<i);
			}
		}
	}
	printf("%d",lim);	
}

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