Submission #1305195

#TimeUsernameProblemLanguageResultExecution timeMemory
1305195snasibov05Bali Sculptures (APIO15_sculpture)C++20
46 / 100
15 ms660 KiB
#include <bits/stdc++.h>

using namespace std;

#define oo 1000000000000000000ll

int main() {
    int n, a, b; cin >> n >> a >> b;
    vector<int> y(n+1);
    for (int i = 1; i <= n; ++i) cin >> y[i];

    vector<long long> pref(n+1);
    for (int i = 1; i <= n; ++i) pref[i] = pref[i-1] + 1ll*y[i];

    const int mx = 35;
    long long ans = 0;
    for (int bt = mx-1; bt >= 0 && n <= 100; --bt){
        vector<vector<bool>> dp(n+1, vector<bool>(b+1)); dp[0][0] = true;
        ans = ans | (1ll << bt);
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= min(i, b); ++j){
                for (int prev = 0; prev < i; ++prev){
                    if (!((pref[i] - pref[prev]) & ans) && dp[prev][j-1]) dp[i][j] = true;
                }
            }
        }

        bool flag = false;
        for (int i = a; i <= b; ++i){
            if (dp[n][i]) flag = true;
        }

        if (!flag) ans = ans ^ (1ll << bt);
    }

    for (int bt = mx-1; bt >= 0 && n > 100; --bt){
        vector<int> dp(n+1, n+1); dp[0] = 0;
        ans = ans | (1ll << bt);
        for (int i = 1; i <= n; ++i){
            for (int prev = 0; prev < i; ++prev){
                if (!((pref[i] - pref[prev]) & ans)) dp[i] = min(dp[i], dp[prev] + 1);
            }
        }

        if (dp[n] > b) ans = ans ^ (1ll << bt);
    }

    ans = ans ^ ((1ll << mx) - 1ll);
    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...