Submission #846045

#	Time	Username	Problem	Language	Result	Execution time	Memory
846045		vjudge1	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	74 ms	660 KiB

sculpture

#include <bits/stdc++.h>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
const int LG=41;
long long n, a[2005], s[2005], p, q, tmp=(1ll<<41)-1;
void sub1()
{
    bool dp[105][105];
    for(int bit = LG-1; bit >= 0; bit--)
    {
        tmp-=1ll<<bit;
        memset(dp, 0, sizeof(dp));
        dp[0][0]=1;
        for(int j = 1; j <= q; j++)
        {
            for(int i = 1; i <= n; i++)
            {
                for(int k = 1; k <= i; k++)
                {
                    if(dp[k-1][j-1] && ((s[i]-s[k-1])|tmp)==tmp)
                        dp[i][j]=1;
                }
            }
        }
        bool ok=0;
        for(int i = p; i <= q; i++)
            if(dp[n][i])
            ok=1;
        if(!ok)
            tmp+=1ll<<bit;
    }
    cout<<tmp;
}
void sub2()
{
    int dp[2005];
    for(int bit = LG-1; bit >= 0; bit--)
    {
        tmp-=1ll<<bit;
        memset(dp, 0x3f, sizeof(dp));
        dp[0]=0;
        for(int i = 1; i <= n; i++)
        {
            for(int k = 1; k <= i; k++)
            {
                if(((s[i]-s[k-1])|tmp)==tmp)
                    dp[i]=min(dp[i], dp[k-1]+1);
            }
        }
        if(dp[n]>q)
            tmp+=1ll<<bit;
    }
    cout<<tmp;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>p>>q;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    if(n<=100)
        sub1();
    else sub2();
}

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