Submission #17341

#	Time	Username	Problem	Language	Result	Execution time	Memory
17341		comet	Bali Sculptures (APIO15_sculpture)	C++98	71 / 100	1000 ms	214448 KiB

sculpture

#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[40][101][101][101];
bool chk2[40][2001][2001];

int K;

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

inline 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[K][x][p][cnt])return ret;
	ret=0;
	chk[K][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("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}

	lim=(1ll<<40)-1;
	
	if(A==1){
		for(int i=39;i>=0;i--){
			K=i;
			lim^=(1ll<<i);
			if(f(1,0)>B){
				lim^=(1ll<<i);
			}
		}
	}else{
		for(int i=39;i>=0;i--){
			K=i;
			lim^=(1ll<<i);
			if(!f(1,0,1)){
				lim^=(1ll<<i);
			}
		}
	}
	printf("%lld",lim);	
}

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