Submission #243056

#	Time	Username	Problem	Language	Result	Execution time	Memory
243056		HuyQuang_re_Zero	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	106 ms	504 KiB

sculpture

#include <bits/stdc++.h>
#define N 2002
using namespace std;
int n,A,B,i,j,k,f[N],dp[102][102];
long long tt,a[N];
bool check(long long tt,int k)
{
    memset(f,63,sizeof(f));
    f[0]=0;
    for(i=1;i<=n;i++)
        for(j=0;j<i;j++)
        {
            long long tt2=a[i]-a[j];
            if(((tt2>>k)|(tt>>k))==(tt>>k)) f[i]=min(f[i],f[j]+1);
        }
    return f[n]<=B;
}
void sub1()
{
    for(k=41;k>=0;k--)
        if(check(tt,k)==0) tt|=(1LL<<k);
    cout<<tt;
}
bool check2(long long tt,int k)
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(i=1;i<=n;i++)
        for(int sl=1;sl<=i;sl++)
        {
            for(j=0;j<i;j++)
            {
                long long tt2=a[i]-a[j];
                if(((tt2>>k)|(tt>>k))==(tt>>k))
                    dp[i][sl]|=dp[j][sl-1];
            }
            if(i==n && A<=sl && sl<=B && dp[i][sl]==1) return 1;
        }
    return 0;
}
void sub2()
{
    for(k=41;k>=0;k--)
        if(check2(tt,k)==0) tt|=(1LL<<k);
    cout<<tt;
}
int main()
{
   // freopen("ntu.inp","r",stdin);
  //  freopen("ntu.out","w",stdout);
    cin>>n>>A>>B;
    for(i=1;i<=n;i++) { cin>>a[i]; a[i]+=a[i-1]; }
 //   sub2(); return 0;
    if(A==1) sub1();
    else sub2();
}

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