Submission #621238

#	Time	Username	Problem	Language	Result	Execution time	Memory
621238		daisy2	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1074 ms	4308 KiB

sculpture

#include<iostream>
#include<cstring>
#define endl '\n'
using namespace std;
long long n,a,b,m[2005],r,pref[2005],ts;
bool dp[2005][2005];
bool isposs(long long num)
{
    for(long long i=0;i<=2000;i++)
        memset(dp[i],0,sizeof(dp[i]));

    dp[0][0]=1;
    bool is=0;
    for(long long i=1;i<=n;i++)
    {
        for(long long j=i;j>=1;j--)
        {
            ts=pref[i]-pref[j-1];
            is=0;
            //if(ts>num) continue;
            for(long long bit=45;bit>=0;bit--)
            {
                if((((long long)1<<bit)&num)==0 && (((long long)1<<bit)&ts)==((long long)1<<bit))
                {
                    is=1;break;
                }
            }
            if(is==1) continue;

            for(long long brg=1;brg<=min(j,b);brg++)
            {
                dp[i][brg]|=dp[j-1][brg-1];
            }
        }
    }
    for(long long i=a;i<=b;i++)
    {
       if(dp[n][i]==1) return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>a>>b;

    for(long long i=1;i<=n;i++)
    {
        cin>>m[i];

        pref[i]=pref[i-1]+m[i];
    }

    r=(((long long)1<<46)-1);

    for(long long i=45;i>=0;i--)
    {
        r^=((long long)1<<i);//cout<<i<<" "<<r<<endl;
        if(isposs(r)==0)
        {
            r|=((long long)1<<i);
        }
    }
  cout<<r<<endl;
}
/*
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: 0 / 29