Submission #1301672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301672		chandan_159	Bali Sculptures (APIO15_sculpture)	C++20	0 / 100	1 ms	572 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF_INT = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, A, B;
    if (!(cin >> N >> A >> B)) return 0;
    vector<ll> Y(N+1);
    for (int i = 1; i <= N; ++i) cin >> Y[i];

    // prefix sums
    vector<ll> ps(N+1, 0);
    for (int i = 1; i <= N; ++i) ps[i] = ps[i-1] + Y[i];

    // maximum bit to inspect (highest bit present in total sum)
    ll total = ps[N];
    int maxbit = 0;
    if (total > 0) maxbit = 63 - __builtin_clzll(total); // highest set bit index
    // we also allow a few extra bits safely (not necessary but harmless)
    // build answer greedily
    ll ans = 0;

    auto feasible = [&](ll mask)->bool{
        // We want to check whether it's possible to partition into X groups with A <= X <= B
        // such that each group's sum has no bits outside mask:
        // i.e., for every group sum S: (S & ~mask) == 0.

        // dpmin[i] = minimum groups to cover prefix length i (0..N)
        // dpmax[i] = maximum groups to cover prefix length i
        vector<int> dpmin(N+1, INF_INT);
        vector<int> dpmax(N+1, -INF_INT);
        dpmin[0] = 0;
        dpmax[0] = 0;

        for (int i = 1; i <= N; ++i) {
            for (int j = 0; j < i; ++j) {
                ll seg = ps[i] - ps[j];
                if ((seg & ~mask) == 0) {
                    // valid segment [j+1..i]
                    dpmin[i] = min(dpmin[i], dpmin[j] + 1);
                    dpmax[i] = max(dpmax[i], dpmax[j] + 1);
                }
            }
        }

        if (dpmin[N] == INF_INT) return false; // no valid partition at all
        // there exists X in [A,B] iff minimal groups <= B and maximal groups >= A
        return (dpmin[N] <= B && dpmax[N] >= A);
    };

    // try bits from high to low
    for (int b = maxbit; b >= 0; --b) {
        // try keep this bit 0: test with current ans (no addition of this bit)
        // if NOT feasible, we must set this bit in ans
        if (!feasible(ans)) {
            ans |= (1LL << b);
        }
        // after possibly setting, we need to test next lower bit.
        // Note: we intentionally test feasibility before adding this bit,
        // thus we only add the bit if necessary.
    }

    // final check: if still not feasible (rare), try to set remaining bits up to maxbit again
    if (!feasible(ans)) {
        // attempt to set any lower bits if needed (safeguard)
        for (int b = 0; b <= maxbit; ++b) {
            if (! (ans & (1LL<<b)) ) {
                ans |= (1LL<<b);
                if (feasible(ans)) break;
            }
        }
    }

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

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