Submission #514916

#	Time	Username	Problem	Language	Result	Execution time	Memory
514916		status_coding	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	169 ms	332 KiB

sculpture

#include <iostream>

using namespace std;

long long n,a,b,ans;
long long v[2005], s[2005];

int dp[2005];
bool dp2[105][105];

bool checkMare()
{
    dp[0]=0;

    for(int i=1;i<=n;i++)
    {
        dp[i]=n+1;

        for(int j=0;j<i;j++)
        {
            long long nval = s[i]-s[j];

            if((nval|ans) == ans)
                dp[i]=min(dp[i], dp[j]+1);
        }
    }

    return dp[n] <= b;
}

bool checkMic()
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            dp2[i][j]=false;

    dp2[0][0]=true;

    for(int nr=1;nr<=b;nr++)
    {
        for(int i=1;i<=n;i++)
            for(int j=0;j<i;j++)
            {
                long long nval = s[i]-s[j];

                if((nval|ans) == ans && dp2[j][nr-1])
                    dp2[i][nr]=true;
            }
    }

    for(int nr=a;nr<=b;nr++)
        if(dp2[n][nr])
            return true;

    return false;
}

bool ok()
{
    if(n <= 100)
        return checkMic();
    else
        return checkMare();
}
int main()
{
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)
        cin>>v[i];

    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+v[i];

    for(int b=0;b<=50;b++)
        ans += ((long long)1 <<b);

    for(int b=50;b>=0;b--)
    {
        ans ^= ((long long)1<<b);

        if(!ok())
            ans ^= ((long long)1<<b);
    }

    cout<<ans;
    return 0;
}

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