Submission #1361463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361463		ezzzay	Bali Sculptures (APIO15_sculpture)	C++20	71 / 100	1095 ms	444 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=50;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=50;x>=0;x--){
        // odoo ehnii hediig dagaad 
        vector<vector<bool>> dp(n+10,vector<bool>(n+10));
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){ // how many groups 
                for(int p=1;p<=i;p++){
                    // p ees i hurtelh 
                    int s=ps[i]-ps[p-1];
                    
                    if(check(s, x)){
                        
                        dp[i][j]= dp[p-1][j-1] ? 1 : dp[i][j];
                        // we formed a new group
                    }
                }
            }
        }
        bool u=0;
        for(int i=A;i<=B;i++){
            if(dp[n][i])u=1;
        }
        if(u==0){
            vis[x]=1;
            //x deh bit zaavl ashiglagdana 
        }
        
    }
    int ans=0;
    for(int i=50;i>=0;i--){
        if(vis[i]){
            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