Submission #1298860

#TimeUsernameProblemLanguageResultExecution timeMemory
1298860AbdullahIshfaqBali Sculptures (APIO15_sculpture)C++20
0 / 100
1 ms572 KiB
//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;
}
#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...