Submission #320615

#	Time	Username	Problem	Language	Result	Execution time	Memory
320615		IloveN	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	245 ms	868 KiB

sculpture

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=2e3+10;
const int inf=1e9;
ll n,A,B,a[N];

void read()
{
    cin>>n>>A>>B;
    for (int i=1;i<=n;i++) cin>>a[i];
}

int dp[N][N];

bool check(ll mask)
{
    dp[0][0]=1;
    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<=i;j++) {
            ll t=a[i];
            for (int k=i-1;k>=0;k--)
            {
                if ((t & mask) == t) dp[i][j] |= dp[k][j-1];
                t+=a[k];
            }
        }
    int res=0;
    for (int i=A;i<=B;i++) res |= dp[n][i];
    return res;
}

void sub1()
{
    ll res=((ll)1<<60)-1;
    for (int i=59;i>=0;i--)
        if (check(res ^ ((ll)1<<i))) res^=((ll)1<<i);
    cout<<res;
}

int dp2[N];

bool check2(ll mask)
{
    for (int i=1;i<=n;i++)
    {
        dp2[i]=inf;
        ll t=a[i];
        for (int j=i-1;j>=0;j--)
        {
            if ((t & mask)==t) dp2[i]=min(dp2[i],dp2[j]+1);
            t+=a[j];
        }
    }
    return (dp2[n]<=B);
}

void sub2()
{
    ll res=((ll)1<<60)-1;
    for (int i=59;i>=0;i--)
        if (check2(res ^ ((ll)1<<i))) res^=((ll)1<<i);
    cout<<res;
}

int main()
{
    //freopen("ss.inp","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    read();
    if (A==1) sub2();
    else sub1();
    return 0;
}

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