| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1298871 | AbdullahIshfaq | Bali Sculptures (APIO15_sculpture) | C++20 | 0 ms | 0 KiB |
// gemini code
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// Maximum number of groups N (or B) is 100 in Subtask 4
const int MAXN = 105;
const int MAX_GROUPS = 105;
// DP table for feasibility check: dp[i][j] is true if the first i sculptures can be partitioned
// into j groups such that the OR-sum of all groups respects the 'target_or' prefix.
bool dp[MAXN][MAX_GROUPS];
// Check function for the feasibility of an OR-sum.
// current_prefix: the required upper bound for the final OR-sum.
bool check(int N, int A, int B, const vector<long long>& Y, long long current_prefix) {
// 1. Calculate prefix sums for O(1) range sum calculation
vector<long long> prefix_sum(N + 1, 0);
for (int i = 0; i < N; ++i) {
prefix_sum[i + 1] = prefix_sum[i] + Y[i];
}
// 2. Initialize DP table: dp[i][j] = false (cannot reach state i with j groups)
for (int i = 0; i <= N; ++i) {
for (int j = 0; j <= B; ++j) {
dp[i][j] = false;
}
}
// Base case: 0 sculptures, 0 groups is possible.
dp[0][0] = true;
// 3. Dynamic Programming
// i: end position of the overall partition (1 to N)
for (int i = 1; i <= N; ++i) {
// j: number of groups used so far (1 to B)
for (int j = 1; j <= B; ++j) {
// k: end position of the *previous* group (0 to i-1)
for (int k = 0; k < i; ++k) {
if (dp[k][j - 1]) {
// Current group is from k+1 to i
long long group_sum = prefix_sum[i] - prefix_sum[k];
// Condition Check: (S OR P) = P
// This is equivalent to: (S & ~P) == 0
// Ensures that group_sum S does not have any bit set that we have committed
// to be 0 (i.e., bits in the region ~current_prefix)
if ((group_sum | current_prefix) == current_prefix) {
dp[i][j] = true;
// Optimization: once dp[i][j] is true, break inner loops
break;
}
}
}
}
}
// 4. Feasibility Result
// Check if the full partition (N sculptures) is possible with A <= groups <= B
for (int j = A; j <= B; ++j) {
if (dp[N][j]) {
return true;
}
}
return false;
}
void solve() {
int N, A, B;
if (!(cin >> N >> A >> B)) return;
vector<long long> Y(N);
long long total_sum = 0;
for (int i = 0; i < N; ++i) {
cin >> Y[i];
total_sum += Y[i];
}
// The maximum possible OR-sum is bounded by total_sum.
// We search from the MSB of total_sum down to bit 0.
int max_bits = 0;
if (total_sum > 0) {
max_bits = 63 - __builtin_clzll(total_sum); // Find the position of the MSB
}
long long min_or_sum = 0;
// Greedy Bit-by-Bit Search
for (int k = max_bits; k >= 0; --k) {
// Current guaranteed prefix of the answer is min_or_sum.
// 1. Try to set the k-th bit to 0.
// The check function must ensure that all group sums S are submasks of min_or_sum
// (for bits > k) AND all bits < k (which we don't care about yet).
// Since min_or_sum is the committed answer so far, passing it to check ensures that
// no group sum violates the "0" bits we have already fixed in higher positions.
if (check(N, A, B, Y, min_or_sum)) {
// Case 1: Possible to achieve the current OR-sum prefix (with bit k as 0).
// min_or_sum remains unchanged (k-th bit is 0).
continue;
} else {
// Case 2: IMPOSSIBLE to achieve the current OR-sum prefix (with bit k as 0).
// The k-th bit MUST be 1. We commit to 1 and update the prefix.
min_or_sum |= (1LL << k);
}
}
cout << min_or_sum << endl;
}
// int main() {
// // For testing with Sample Input: 6 1 3 | 8 1 2 1 5 4 -> Output: 11
// solve();
// return 0;
// }