Submission #17343

#	Time	Username	Problem	Language	Result	Execution time	Memory
17343		comet	Bali Sculptures (APIO15_sculpture)	C++98	100 / 100	139 ms	1132 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];
int d2[2001];

int f(int D){
	switch(D){
	case 1:
		for(int i=1;i<=N;i++){
			d2[i]=1e9;
			for(int j=0;j<i;j++){
				if(((sum[i]-sum[j])|lim)==lim){
					d2[i]=min(d2[i],d2[j]+1);
				}
			}
		}
		return d2[N];
	case 2:
		for(int i=1;i<=N;i++){
			d[1][i]=0;
			if((sum[i]|lim)==lim)d[1][i]=1;
		}
		for(int k=2;k<=B;k++){
			for(int i=1;i<=N;i++){
				d[k][i]=0;
				for(int j=k-1;j<i;j++){
					if(((sum[i]-sum[j])|lim)==lim){
						d[k][i]|=d[k-1][j];
					}
				}
			}
		}
		for(int i=A;i<=B;i++){
			if(d[i][N])return 1;
		}
		return 0;
	}
	return 0;
}

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<<45)-1;

	if(A==1){
		for(int i=44;i>=0;i--){
			lim^=(1ll<<i);
			if(f(1)>B){
				lim^=(1ll<<i);
			}
		}
	}else{
		for(int i=44;i>=0;i--){
			lim^=(1ll<<i);
			if(!f(2)){
				lim^=(1ll<<i);
			}
		}
	}

	printf("%lld",lim);	
}

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