//gpt code // Bali Sculptures - APIO 2015 P1 // Full solution: greedy on bits + DP check for minimal group count // Complexity: O(N^2 * bits) where bits ~ 0..60 (safe) // Based on the editorial approach. (DMOJ editorial). :contentReference[oaicite:10]{index=10} #include <bits/stdc++.h> using namespace std; using int64 = long long; const int INF = 1e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); #if defined(LOCAL) freopen("input.txt","r",stdin); #endif int N; int A, B; if (!(cin >> N >> A >> B)) return 0; vector<int64> Y(N+1); for (int i = 1; i <= N; ++i) cin >> Y[i]; // prefix sums (1-based) vector<int64> pref(N+1, 0); for (int i = 1; i <= N; ++i) pref[i] = pref[i-1] + Y[i]; // Maximum possible sum int64 total = pref[N]; // We'll test bits from high down to 0. Choose upper bound safely, e.g., 0..60. int HIGH = 0; if (total > 0) HIGH = 63 - __builtin_clzll((unsigned long long)total); // index of highest set bit else HIGH = 0; int64 ans = 0; // current bits fixed to 1 in the answer // For each bit from HIGH down to 0, try to keep it 0 for (int bit = HIGH; bit >= 0; --bit) { // candidate mask: bits we already set to 1 in ans (we *do not* set current bit) int64 allowed = ans; // we try to keep current bit = 0 => not adding (1LL<<bit) // DP: dp[j] = minimal number of groups to partition first j elements (0..j) vector<int> dp(N+1, INF); dp[0] = 0; for (int i = 0; i < N; ++i) { if (dp[i] == INF) continue; // extend group from i+1..j for (int j = i+1; j <= N; ++j) { int64 sum = pref[j] - pref[i]; // sum is allowed if it doesn't set any bit outside 'allowed' // i.e., (sum & ~allowed) == 0 if ((sum & ~allowed) == 0) { if (dp[j] > dp[i] + 1) dp[j] = dp[i] + 1; } } } // If it's possible to partition with at most B groups (and >= A ideally), // then we can keep this bit 0. Otherwise we must set it to 1. if (dp[N] <= B) { // feasible leaving current bit 0 -> nothing to do } else { // must set current bit to 1 ans |= (1LL << bit); } } cout << ans << '\n'; return 0; }