Submission #404594

#	Time	Username	Problem	Language	Result	Execution time	Memory
404594		sad	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	198 ms	452 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=109;
int n,a,b;
int aa[N],dp[N][N];ll mask=0;
int d(int x,int o)
{
    if(x==n&&o>=a&&o<=b)return 1;
    if(x==n)return 0;
    int &u=dp[x][o];
    if(u!=-1)return u;
    u=0;ll sum=0;
    for(int j=x;j<n;j++)
    {
        sum+=aa[j];
        if((sum&mask))continue;
        u=max(u,d(j+1,o+1));
    }
    return u;
}
int ch(ll s)
{
    mask=s;
    memset(dp,-1,sizeof dp);
    int u=d(0,0);
    if(u)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=40;i>-1;i--)
    {
        if(ch(r+(u<<i))){
            r+=(u<<i);continue;
        }
        else re+=(u<<i);
    }
    cout<<re;

}

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