Submission #404595

#	Time	Username	Problem	Language	Result	Execution time	Memory
404595		sad	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	248 ms	420 KiB

sculpture

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N=2009;
int n,a,b;
int aa[N],dp[N];ll mask=0;
int d(int x)
{
    if(x==n)return 0;
    int &u=dp[x];
    if(u!=-1)return u;
    u=1e9;ll sum=0;
    for(int j=x;j<n;j++)
    {
        sum+=aa[j];
        if((sum&mask))continue;
        u=min(u,d(j+1)+1);
    }
    return u;
}
int ch(ll s)
{
    mask=s;
    memset(dp,-1,sizeof dp);
    int u=d(0);
    if(u<=b)return 1;
    return 0;
}
int main()
{
    ll re=0;
    cin>>n>>a>>b;
    for(int i=0;i<n;i++)cin>>aa[i];
    ll r=0;ll u=1;
    for(int i=50;i>-1;i--)
    {
        if(ch(r+(u<<i))){
            r+=(u<<i);continue;
        }
        else re+=(u<<i);
    }
    cout<<re;

}

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