Submission #1153587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153587		AlgorithmWarrior	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	50 ms	436 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

int const MAX1=105;
int const MAX2=2005;
bool dp1[MAX1][MAX1];
int dp2[MAX2];
int n,a,b;
int v[MAX2];

void read(){
    cin>>n>>a>>b;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
}

bool check1(long long nr){
    int i,j,l;
    for(i=0;i<=n;++i)
        for(j=0;j<=n;++j)
            dp1[i][j]=0;
    dp1[0][0]=1;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j){
            long long sum=v[i];
            for(l=i-1;l>=0;sum+=v[l],--l)
                if(dp1[l][j-1] && (sum|nr)==nr)
                    dp1[i][j]=1;
        }
    bool ok=0;
    for(j=a;j<=b;++j)
        ok|=dp1[n][j];
    return ok;
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

bool check2(long long nr){
    dp2[0]=0;
    int i,j;
    for(i=1;i<=n;++i){
        dp2[i]=b+1;
        long long sum=v[i];
        for(j=i-1;j>=0;sum+=v[j],--j)
            if((sum|nr)==nr)
                minself(dp2[i],dp2[j]+1);
    }
    return (dp2[n]<=b);
}

long long solve(){
    long long ans=0;
    int i;
    for(i=40;i>=0;--i)
        if(n<=100){
            if(!check1(ans+(1LL<<i)-1))
                ans+=(1LL<<i);
        }
        else{
            if(!check2(ans+(1LL<<i)-1))
                ans+=(1LL<<i);
        }
    return ans;
}

int main()
{
    read();
    cout<<solve();
    return 0;
}

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