Submission #708866

#	Time	Username	Problem	Language	Result	Execution time	Memory
708866		ToroTN	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	213 ms	460 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a,b,c,qs[2005],dp[2005],cnt,dp2[105][105];
ll query(ll l,ll r)
{
    return qs[r]-qs[l-1];
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> a >> b;
    for(int i=1;i<=n;i++)
    {
        cin >> c;
        qs[i]=qs[i-1]+c;
    }
    if(a==1)
    {
        cnt=0;
        for(int i=60;i>=0;i--)
        {
            cnt|=(1ll<<i);
            for(int j=1;j<=n;j++)dp[j]=1e9;
            dp[0]=0;
            for(int j=1;j<=n;j++)
            {
                for(int k=0;k<j;k++)
                {
                    if((query(k+1,j)&cnt)==0)
                    {
                        dp[j]=min(dp[j],dp[k]+1);
                    }
                }
            }
            if(dp[n]>b)cnt^=(1ll<<i);
        }
        printf("%lld\n",(((1ll<<61)-1ll)^cnt));
    }else
    {
        for(int i=60;i>=0;i--)
        {
            //printf("%d\n",i);
            cnt|=(1ll<<i);
            for(int j=0;j<=n;j++)
            {
                for(int k=0;k<=j;k++)
                {
                    //printf("%d %d\n",j,k);
                    dp2[j][k]=0;
                }
            }
            dp2[0][0]=1;
            for(int j=1;j<=n;j++)
            {
                for(int k=0;k<j;k++)
                {
                    if((query(k+1,j)&cnt)==0)
                    {
                        for(int l=1;l<=j;l++)
                        {
                            if(dp2[k][l-1]==1)
                            {
                                dp2[j][l]=1;
                            }
                        }
                    }
                }
            }
            int sum=0;
            for(int j=a;j<=b;j++)sum+=dp2[n][j];
            if(sum==0)
            {
                cnt^=(1ll<<i);
            }
        }
        printf("%lld\n",(((1ll<<61)-1ll)^cnt));
    }
}

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