Submission #1153584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153584		AlgorithmWarrior	Bali Sculptures (APIO15_sculpture)	C++20	71 / 100	18 ms	636 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;
}

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);
        }
    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: 0 / 29