Submission #1345718

#TimeUsernameProblemLanguageResultExecution timeMemory
1345718killerzaluuBali Sculptures (APIO15_sculpture)C++20
100 / 100
34 ms476 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, A, B;
    cin >> n >> A >> B;

    vector<long long> y(n + 1), pref(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> y[i];
        pref[i] = pref[i - 1] + y[i];
    }

    auto ok_sum = [&](long long sum, long long mask) {
        return (sum | mask) == mask;
    };

    auto check_small = [&](long long mask) {
        static bool dp[105][105];
        for (int i = 0; i <= n; i++) {
            for (int k = 0; k <= n; k++) {
                dp[i][k] = false;
            }
        }

        dp[0][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                long long sum = pref[i] - pref[j];
                if (!ok_sum(sum, mask)) continue;
                for (int k = 1; k <= B; k++) {
                    if (dp[j][k - 1]) dp[i][k] = true;
                }
            }
        }

        for (int k = A; k <= B; k++) {
            if (dp[n][k]) return true;
        }
        return false;
    };

    auto check_big = [&](long long mask) {
        const int INF = 1e9;
        vector<int> dp(n + 1, INF);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                long long sum = pref[i] - pref[j];
                if (!ok_sum(sum, mask)) continue;
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }

        return dp[n] <= B;
    };

    long long ans = (1LL << 41) - 1;

    for (int b = 40; b >= 0; b--) {
        long long cand = ans ^ (1LL << b);

        bool good;
        if (A == 1) good = check_big(cand);
        else good = check_small(cand);

        if (good) ans = cand;
    }

    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...