Submission #976916

#	Time	Username	Problem	Language	Result	Execution time	Memory
976916		nnin	Bali Sculptures (APIO15_sculpture)	C++17	71 / 100	1022 ms	13324 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define piv pair<int,set<int>>

int N, A, B;
ll sum[2005], dp[2005][2005];

bool check(ll x) {
    vector<piv> idx;
    idx.push_back({0, {0}});
    for(int i=1;i<=N;i++) {
        set<int> tmp;
        for(auto [j, s]:idx) {
            ll ss = sum[i]-sum[j];
            if((ss|x)==x && (ss&x)==ss) {
                for(int ctt:s) if(ctt<B) tmp.insert(ctt+1);
            }
        }
        if(!tmp.empty()) idx.push_back({i, tmp});
    }
    if(idx.back().first<N) return false;
    for(int s:idx.back().second) if(s>=A && s<=B) return true;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>N>>A>>B;
    for(int i=1;i<=N;i++) cin>>sum[i], dp[i][0] = sum[i] += sum[i-1];
    ll ans = (1ll<<51)-1;
    for(int i=50;i>=0;i--) {
        ans ^= (1ll<<i);
        if(!check(ans)) {
            ans ^= (1ll<<i);
        }
    }
    cout<<ans;
}

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