Submission #1357825

#TimeUsernameProblemLanguageResultExecution timeMemory
1357825AgageldiBali Sculptures (APIO15_sculpture)C++17
37 / 100
64 ms768 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 | ((1<<i) - 1);
        if(!check(num)){
            // cout << i <<"<-" << '\n';
            M |= (1 << 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...