Submission #369294

#	Time	Username	Problem	Language	Result	Execution time	Memory
369294		Bill_00	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	294 ms	512 KiB

sculpture

#include <bits/stdc++.h>
typedef long long ll;
#define N 2005
using namespace std;
ll x[N],n,a,b,sum[N];
bool dp[N][N];
int dpp[N];
bool check(ll mask){
	if(a>1){
		for(ll i=1;i<=n;i++){
			for(ll j=1;j<=n;j++){
				dp[i][j]=0;
			}
		}
		dp[0][0]=1;
		for(ll i=1;i<=n;i++){
			for(ll j=1;j<=i;j++){
				for(ll k=1;k<=i;k++){
					if(dp[k-1][j-1]==1 && ((mask)&(sum[i]-sum[k-1]))==(sum[i]-sum[k-1])){
						dp[i][j]=1;
					}
				}
			}
		}
		for(ll i=a;i<=b;i++){
			if(dp[n][i]==1) return 1;
		}
		return 0;
	}
	else{
		dpp[0]=0;
		for(ll i=1;i<=n;i++){
			dpp[i]=n+1;
		}
		for(ll i=1;i<=n;i++){
			for(ll j=1;j<=i;j++){
				if(dpp[j-1]!=n+1 && ((mask)&(sum[i]-sum[j-1]))==(sum[i]-sum[j-1])){
					dpp[i]=min(dpp[i],dpp[j-1]+1);
				}
			}
		}
		if(dpp[n]<=b) return 1;
		else return 0;
	}
}
int main() {
	cin >> n >> a >> b;
	for(ll i=1;i<=n;i++){
		cin >> x[i];
		sum[i]=sum[i-1]+x[i];
	}
	ll ans=(1LL<<62)-1;
	for(ll i=61;i>=0;i--){
		if(check(ans-(1LL<<i))){
			ans-=(1LL<<i);
		}
	}
	cout << ans;
}

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