Submission #495556

#	Time	Username	Problem	Language	Result	Execution time	Memory
495556		FairyWinx	Bali Sculptures (APIO15_sculpture)	C++17	50 / 100	784 ms	23760 KiB

sculpture

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define SOLVE int t; cin >> t; while (t--) solve();

#define int long long

using namespace std;

const int N = 2e3 + 228;
int good[N][N];
long long pr[N];

bool check(int n, int R, int ind) {
    vector<int> dp(n + 1, n + 228);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (!good[j][i - 1] && !((pr[i] - pr[j]) & (1ll << ind))) {
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[n] <= R;
}

signed main() {
    #ifdef DEBUG
        freopen("main/in.txt", "r", stdin);
    #endif
    #ifndef LOCAL
        ios_base::sync_with_stdio(0);
        cin.tie(0);
    #endif

    int n, L, R;
    cin >> n >> L >> R;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pr[i + 1] = pr[i] + a[i];
    }
    long long ans = 0;
    for (int i = 60; i >= 0; --i) {
        if (!check(n, R, i)) {
            ans += (1ll << i);
        } else {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k <= j; ++k) {
                    if ((pr[j + 1] - pr[k]) & (1ll << i)) {
                        good[k][j] = 1;
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

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