Submission #119136

#	Time	Username	Problem	Language	Result	Execution time	Memory
119136		Charis02	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	91 ms	4480 KiB

sculpture

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 2020
#define INF 1e9+7

using namespace std;

ll n,a,b,ar[N];
bool dp[N][N];
ll dp2[N];
ll psum[N];

ll get_sum(ll i,ll j)
{
    if(i == 0)
        return psum[j];
    return psum[j]-psum[i-1];
}

bool ison(ll m,ll i)
{
    return (m >> i)&1;
}

ll getp(ll b)
{
    if(b <= 20)
        return (1 << b);

    return (getp(b-20) << 20);
}

void solve1()
{
    ll off = 0;

    for(ll bits = 42;bits >= 0;bits--)
    {
        ll check = off;
        check |= getp(bits);

        memset(dp,0,sizeof dp);

        rep(i,0,n)
        {
            if(!(psum[i]&check))
                dp[i][1] = 1;
        }

        rep(i,0,n)
        {
            rep(j,1,i+1)
            {
                if(((get_sum(j,i))&(check)))
                    continue;

                rep(k,2,b+1)
                {
                    if(dp[j-1][k-1])
                        dp[i][k] = 1;
                }
            }
        }

        rep(i,a,b+1)
            if(dp[n-1][i])
                off = check;
    }
    ll ans = 0;

    rep(bits,0,43)
    {
        if(!ison(off,bits))
            ans |= getp(bits);
    }

    cout << ans;
    return;
}

void solve2()
{
    ll off = 0;

    for(ll bits = 42;bits >= 0;bits--)
    {
        ll check = off;
        check |= getp(bits);

        rep(i,0,n)
        {
            if(!(psum[i]&check))
                dp2[i] = 1;
            else
                dp2[i] = n+1;
        }

        rep(i,0,n)
        {
            rep(j,1,i+1)
            {
                if(!(get_sum(j,i)&check))
                    dp2[i] = min(dp2[i],dp2[j-1]+1);
            }
        }

        if(dp2[n-1] <= b)
            off = check;
    }
    ll ans = 0;

    rep(bits,0,43)
    {
        if(!ison(off,bits))
            ans |= getp(bits);
    }

    cout << ans << endl;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> a >> b;

    memset(dp,-1,sizeof dp);

    rep(i,0,n)
    {
        cin >> ar[i];

        if(i == 0)
            psum[i] = ar[i];
        else
            psum[i] = ar[i]+psum[i-1];
    }

    if(n <= 100)
        solve1();
    else
        solve2();

    return 0;
}

/*
6 1 3
8 1 2 1 5 4
*/

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