Submission #1361469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361469		ezzzay	Bali Sculptures (APIO15_sculpture)	C++20	50 / 100	365 ms	460 KiB

sculpture

#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];
    }
    
    for(int x=41;x>=0;x--){
        vector<int>dp(n+10, 10*n);
        dp[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;
                dp[i]= min(dp[i],dp[p-1]+1);
                   
            }
        }
        bool u=dp[n]<=B;
        if(u==0)vis[x]=1;
        
    }
    int ans=0;
    for(int i=41;i>=0;i--){
        if(vis[i])ans+=(1ll<<i);
        
    }
    cout<<ans;
}

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