Submission #866816

#	Time	Username	Problem	Language	Result	Execution time	Memory
866816		1075508020060209tc	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	856 ms	32180 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[2010][2010];
int ar[2010];
int ps[2010];
int A;int B;
int n;
int ok(int msk){
dp[0][0]=1;
for(int k=1;k<=B;k++){
    for(int i=1;i<=n;i++){
        dp[k][i]=0;
    }
    vector<int>vc;
    if(dp[k-1][0]){vc.push_back(0);}
    for(int i=1;i<=n;i++){
        for(int j=(int)vc.size()-1;j>=0;j--){
            int v=ps[i]-ps[vc[j]];
            if( ((v|msk)==msk) ){
                dp[k][i]=1;break;
            }
        }
        if(dp[k-1][i]){
            vc.push_back(i);
        }
    }
    if(dp[k][n]==1&&k>=A){return 1;}
}
return 0;

}


signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);

cin>>n>>A>>B;
for(int i=1;i<=n;i++){
    cin>>ar[i];
    ps[i]=ar[i]+ps[i-1];
}
int msk=(1ll<<46)-1;

for(int bt=45;bt>=0;bt--){
    if(ok(msk^(1ll<<bt))){
        msk^=(1ll<<bt);
    }
}
cout<<msk;

}

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