Submission #131023

#	Time	Username	Problem	Language	Result	Execution time	Memory
131023		someone_aa	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	160 ms	508 KiB

sculpture

#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 2100;
ll n, a, b;
ll arr[maxn];
ll dp[maxn];

bool dp2[110][110];

bool check(ll mask) {
	dp[0] = 0LL;
	for(int i=1;i<=n;i++) {
		ll sum = 0LL;
		dp[i] = INT_MAX;
		for(int lst=i;lst>=1;lst--) {
			sum += arr[lst];
			if((sum & mask) == sum) {
				dp[i] = min(dp[i], dp[lst-1] + 1);
			}
		}
	}

	return dp[n] <= b;
}

bool check100(ll mask) {
	memset(dp2, false, sizeof(dp2));
	dp2[0][0] = true;

	for(int p=1;p<=b;p++) {
		for(int i=1;i<=n;i++) {
			ll sum = 0LL;
			for(int lst=i;lst>=1;lst--) {
				sum += arr[lst];

				if((sum&mask)==sum) dp2[p][i] |= dp2[p-1][lst-1];
			}
		}
	}

	bool check = false;
	for(int i=a;i<=b;i++) {
		check |= dp2[i][n];
	}
	return check;
}

int main() {
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) {
		cin>>arr[i];
	}

	if(n <= 100) {
		ll mask = 0LL;
		for(ll bit=50LL;bit>=0;bit--) {
			ll temp_mask = mask + ((1LL<<bit) - 1);
			//cout<<temp_mask<<": "<<check(temp_mask)<<"\n";
			if(!check100(temp_mask)) mask += (1LL<<bit);
		}
		cout<<mask<<"\n";
		return 0;
	}

	ll mask = 0LL;
	for(ll bit=50LL;bit>=0;bit--) {
		ll temp_mask = mask + ((1LL<<bit) - 1);
		//cout<<temp_mask<<": "<<check(temp_mask)<<"\n";
		if(!check(temp_mask)) mask += (1LL<<bit);
	}
	cout<<mask<<"\n";
}

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