Submission #1110445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110445		simona1230	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	102 ms	2744 KiB

sculpture

#include <bits/stdc++.h>

using namespace std;

long long n,a,b;
long long c[2001],p[2001];
long long dp[2001][2001];

bool check(long long x)
{
    //cout<<"! "<<x<<endl;
    dp[0][0]=1;
    for(long long i=1;i<=n;i++)
    {
        for(long long j=1;j<=n;j++)
        {
            dp[i][j]=0;
            for(long long k=0;k<i;k++)
            {
                if(p[i]-p[k]>x)continue;
                if(((p[i]-p[k])|x)<=x)
                {
                    //cout<<p[i]-p[k]<<endl;
                    dp[i][j]=max(dp[i][j],dp[k][j-1]);
                }
            }

            //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            if(i==n&&j>=a&&j<=b&&dp[i][j])
            {
                return 1;
            }
        }
    }

    return 0;
}

int dp1[2001];

bool check1(long long x)
{
    for(int i=1;i<=n;i++)
    {
        dp1[i]=b+1;
        for(int j=0;j<i;j++)
        {
            if(((p[i]-p[j])|x)<=x)
            {
                dp1[i]=min(dp1[i],dp1[j]+1);
            }
        }
    }

    if(dp1[n]<=b)return 1;
    return 0;
}

void read()
{
    cin>>n>>a>>b;
    for(long long i=1;i<=n;i++)
    {
        cin>>c[i];
        p[i]=p[i-1]+c[i];
    }
}

long long w[64];
void solve()
{
    w[0]=1;
    for(int i=1;i<=60;i++)
        w[i]=w[i-1]*2;
    long long ans=0;
    for(long long i=60;i>=0;i--)
    {
        long long curr=ans;
        for(long long j=i-1;j>=0;j--)
            curr+=w[j];

        //cout<<curr<<endl;

        if(a!=1&&!check(curr))ans+=w[i];
        if(a==1&&!check1(curr))ans+=w[i];
    }

    cout<<ans<<endl;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve();
	return 0;
}

/*
6 1 3
8 1 2 1 5 4
*/

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