제출 #979466

#제출 시각아이디문제언어결과실행 시간메모리
979466TranGiaHuy1508Bali Sculptures (APIO15_sculpture)C++17
100 / 100
70 ms604 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...