Submission #914117

#	Time	Username	Problem	Language	Result	Execution time	Memory
914117		12345678	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	128 ms	2648 KiB

sculpture

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
 
const int nx=2e3+5;
ll n, a, b, x, vl[nx], dp[nx][nx], dp2[nx], msk, p[60], m;
 
int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>a>>b;
    p[0]=1;
    for (int i=1; i<60; i++) p[i]=p[i-1]*2;
    m=p[59]-1;
    for (int i=1; i<=n; i++) cin>>vl[i];
    dp[0][0]=1;
    if (a==1)
    {
        for (int x=58; x>=0; x--)
        {
            m-=p[x];
            for (int i=1; i<=n; i++)
            {
                msk=vl[i];
                dp2[i]=1e9;
                for (int j=i-1; j>=0; j--)
                {
                    if ((msk|m)==m) dp2[i]=min(dp2[i], dp2[j]+1);
                    msk+=vl[j];
                }
            }
            if (dp2[n]>b) m+=p[x];
        }
        return cout<<m, 0;
    }
    for (int x=58; x>=0; x--)
    {
        m-=p[x];
        for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dp[i][j]=0;
        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=n; j++)
            {
                msk=vl[i];
                for (int k=i-1; k>=0; k--)
                {
                    if ((msk|m)==m&&dp[k][j-1]) dp[i][j]|=1;
                    msk+=vl[k]; 
                }
            }
        }
        bool can=0;
        for (int j=a; j<=b; j++) can|=dp[n][j];
        if (!can) m+=p[x];
    }
    cout<<m;
}

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