Submission #1357827

#TimeUsernameProblemLanguageResultExecution timeMemory
1357827AgageldiBali Sculptures (APIO15_sculpture)C++17
71 / 100
1096 ms8264 KiB
#include <bits/stdc++.h>
using namespace std;

#define N 2001
#define int long long

const int inf = INT_MAX;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, a[N], B, A, b[N], ans = -1, M = 0;
set <int> dp[N];

bool check(int x) {
    for(int i = 1; i <= n; i++) {
        dp[i].clear();
    }

    dp[0].insert(0);

    for(int i = 0; i <= n; i++) {
        int s = 0;
        if(dp[i].empty()) continue;
        for(int j = i + 1; j <= n; j++){
            s += a[j];
            if(!(s & (~x))){
                for(auto k : dp[i]) {
                    dp[j].insert(k + 1);
                }
            }
        }
    }
    for(auto i : dp[n]) {
        if(i >= A && i <= B) return 1;
    }
    return 0;
}

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> A >> B;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 60; i >= 0; i--) {
        int num = M | ((1ll<<i) - 1);
        if(!check(num)){
            M |= (1ll << i);
        }
    }
    cout << M << '\n';
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...