Submission #1315816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315816		wangzhiyi33	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	79 ms	440 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int LOG = 45;
int angka[2002];
int n,a,b;

bool can(int cur){
    bool dp[n+1][b+1];
    memset(dp,false,sizeof dp);

    dp[0][0]=true;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=b;j++){
            int sum = 0;
            for(int leng=1;leng<=i;leng++){
                // [i-leng+1...i] = sum
                // [..sum1..] OR [..sum2..] OR [..sum3..] OR [..sum4..] = cur
                sum += angka[i-leng+1];
                if((cur|sum)==cur){
                    dp[i][j]|=dp[i-leng][j-1];
                }
            }
        }
    }
    for(int q=a;q<=b;q++){
        if(dp[n][q]==true){
            return true;
        }
    }
    return false;

}

bool can2(int cur){
    int dp[n+1];
    for(int q=1;q<=n;q++){
        dp[q]=1e15;
    }
    dp[0]=0;
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int leng=1;leng<=i;leng++){
            sum+=angka[i-leng+1];
            if((cur|sum)==cur){
                dp[i]=min(dp[i],dp[i-leng]+1);
            }
        }
    }

    if(dp[n]<=b)return true;
    return false;
}

signed main(){
    cin>>n>>a>>b;
    for(int q=1;q<=n;q++){
        cin>>angka[q];
    }

    int x = (1LL<<LOG)-1;
    if(a==1){
        for(int i= LOG-1 ;i>=0 ;i--){
            if(can2(x^(1LL<<i))){
                x=x^(1LL<<i);
            }

        }
        cout<<x<<endl;
        return 0;
    }


    for (int i = LOG-1; i >= 0; i--) {
        if (can(x^(1LL<<i))) {
            x=x^(1LL<<i);
        }
    }
    cout<<x<<endl;
}

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