Submission #337103

#	Time	Username	Problem	Language	Result	Execution time	Memory
337103		bigDuck	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	153 ms	492 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int t, n, m, k, A, B, y[2010];



void A1(){
int dp[2010];


dp[0]=0;
int p=(1ll<<41)-1;

for(int b=40; b>=0; b--){
    p-=(1ll<<b);
    for(int i=1; i<=n; i++){
            dp[i]=-1;
            int sum=0;
        for(int j=i-1; j>=0; j--){
            sum+=y[j+1];
            if( (dp[j]>=0) && ( (sum|p)<=p ) ){
                if(dp[i]==-1){dp[i]=dp[j]+1;}
                else{dp[i]=min(dp[i], dp[j]+1); }
            }
        }
    }

    if( (dp[n]!=(-1)) && (dp[n]<=B) ){
        continue;
    }
    else{
        p+=(1ll<<b);
    }

}



cout<<p;

}




void n3(){
bool dp[110][110];

int p=(1ll<<41)-1;
dp[0][0]=true;
for(int g=1; g<=B; g++){
    dp[0][g]=false;
}

for(int b=40; b>=0; b--){

        p-=(1ll<<b);
    for(int i=1; i<=n; i++){
        for(int g=0; g<=B; g++){
            dp[i][g]=false;;
        }
        int sum=0;
        for(int j=i-1; j>=0; j--){
            sum+=y[j+1];
            for(int g=0; g<B; g++){
                if( ( (sum|p)<=p) ){dp[i][g+1]|=dp[j][g];}
            }
        }

    }

    for(int g=A; g<=B; g++){
        if(dp[n][g]==true){
            goto Next;
        }
    }
    p+=(1ll<<b);
    Next:continue;
}

cout<<p;


}



int32_t main(){
INIT
cin>>n>>A>>B;
for(int i=1; i<=n; i++){
    cin>>y[i];
}


if(A==1){
    A1();
}
else{
    n3();
}



return 0;
}

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