Submission #386693

#	Time	Username	Problem	Language	Result	Execution time	Memory
386693		jjang36524	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	123 ms	512 KiB

sculpture

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
#define int long long
int dp[2001];
int dp2[101][101];
int psum[2001];
signed main()
{
    int N,a,b;
    cin >> N >> a >> b;
    int i;
    for(i=0;i<N;i++)
    {
        int v;
        cin >> v;
        psum[i+1]=psum[i]+v;
    }
    if(a==1)
    {
        int cu=(1LL<<42)-1;
        for(i=41;i>=0;i--)
        {
            cu-=1LL<<i;
            int j;
            memset(dp,1,sizeof(dp));
            dp[0]=0;
            for(j=1;j<=N;j++)
            {
                int k;
                for(k=0;k<j;k++)
                {
                    if(((psum[j]-psum[k])|cu)==cu)
                    {
                        dp[j]=min(dp[j],dp[k]+1);
                    }
                }
            }
            if(dp[N]>b)
                cu+=1LL<<i;
        }
        cout <<cu;
    }
    else
    {
        int cu=(1LL<<42)-1;
        for(i=41;i>=0;i--)
        {
            cu-=1LL<<i;
            int j;
            memset(dp2,0,sizeof(dp2));
            dp2[0][0]=1;
            for(j=1;j<=N;j++)
            {
                int k;
                for(k=0;k<j;k++)
                {
                    if(((psum[j]-psum[k])|cu)==cu)
                    {
                        int l;
                        for(l=0;l<N;l++)
                        {
                            dp2[j][l+1]|=dp2[k][l];
                        }
                    }
                }
            }
            int po=0;
            for(j=a;j<=b;j++)
            {
                po|=dp2[N][j];
            }
             if(!po)
                cu+=1LL<<i;
        }
        cout <<cu;
    }
}

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