Submission #979466

#	Time	Username	Problem	Language	Result	Execution time	Memory
979466		TranGiaHuy1508	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	70 ms	604 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

using ll = long long;

int n, A, B;
vector<int> v;

bool check_normal(ll x){
	vector<vector<int>> dp(n + 1, vector<int>(B + 1, 0));
	dp[0][0] = 1;

	for (int i = 0; i <= n; i++){
		ll sum = 0;
		for (int j = i + 1; j <= n; j++){
			sum += v[j - 1];
			if ((sum & x) == sum){
				for (int blk = 0; blk < B; blk++){
					dp[j][blk + 1] |= dp[i][blk];
				}
			}
		}
	}

	for (int j = A; j <= B; j++){
		if (dp[n][j]) return true;
	}
	return false;
}

bool check_min(ll x){
	vector<int> dp(n + 1, n + 1);
	dp[n] = 0;

	for (int i = n - 1; i >= 0; i--){
		ll sum = 0;
		for (int j = i + 1; j <= n; j++){
			sum += v[j - 1];
			if ((sum & x) == sum){
				dp[i] = min(dp[i], dp[j] + 1);
			}
		}
	}

	return dp[0] <= B;
}

bool check(ll x){
	if (A == 1) return check_min(x);
	return check_normal(x);
}

void main_program(){
	cin >> n >> A >> B;

	v.resize(n);
	for (int i = 0; i < n; i++) cin >> v[i];

	ll ans = (1LL << 42) - 1;

	for (int i = 41; i >= 0; i--){
		if (check(ans ^ (1LL << i))) ans ^= (1LL << i);
	}

	cout << ans << "\n";
}

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