Submission #1361470

#TimeUsernameProblemLanguageResultExecution timeMemory
1361470ezzzayBali Sculptures (APIO15_sculpture)C++20
100 / 100
237 ms480 KiB
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=5555;
int a[N];
int ps[N];
bool vis[55];
bool check(int s, int x){
    for(int i=41;i>=x;i--){
        if((1ll<<i) & s){
            // baigaa 
            if(vis[i]==0)return 0;
        }
    }
    return 1;
}
signed main(){
    int n,A,B;
    cin>>n>>A>>B;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ps[i]=ps[i-1]+a[i];
    }
    int ans=0;
    for(int x=41;x>=0;x--){
        vector<int>dp1(n+10, 10*n);
        vector<int>dp2(n+10, -10*n);
        dp1[0]=0;
        dp2[0]=0;
        for(int i=1;i<=n;i++){
            for(int p=1;p<=i;p++){
                int s=ps[i]-ps[p-1];
                bool u=check(s,x);
                if(u==0)continue;
                dp1[i]= min(dp1[i],dp1[p-1]+1);
                dp2[i]= max(dp2[i],dp2[p-1]+1);
            }
        }
        int l=dp1[n],r=dp2[n];
        bool u=1;
        if(A>r or B<l)u=0;
        if(u==0){
            vis[x]=1;
            ans+=(1ll<<x);
        }
    }
    cout<<ans;
}
#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...