제출 #17339

#제출 시각아이디문제언어결과실행 시간메모리
17339cometBali Sculptures (APIO15_sculpture)C++98
71 / 100
1000 ms22676 KiB
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

ll a[2010];
ll sum[2010];

int N,A,B;
ll 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(){
	//freopen("sculpture.in","r",stdin);
	scanf("%d%d%d",&N,&A,&B);
	for(int i=1;i<=N;i++){
		scanf("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}

	lim=(1ll<<40)-1;

	if(A==1){
		for(int i=39;i>=0;i--){
			memset(chk2,0,sizeof(chk2));
			lim^=(1ll<<i);
			if(f(1,0)>B){
				lim^=(1ll<<i);
			}
		}
	}else{
		for(int i=39;i>=0;i--){
			memset(chk,0,sizeof(chk));
			lim^=(1ll<<i);
			if(!f(1,0,1)){
				lim^=(1ll<<i);
			}
		}
	}
	printf("%lld",lim);	
}
#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...