제출 #660940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660940		danikoynov	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1085 ms	468 KiB

sculpture

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll maxn = 1010, maxbit = 62;

ll n, A, B, f[maxbit], aw[maxn];
ll dp[101][101][2], fp[maxn][2];
ll a[maxn];
void solve()
{
    cin >> n >> A >> B;
    for (ll i = 1; i <= n; i ++)
        cin >> a[i];

    if (A == 1)
    {
        for (ll bit = maxbit - 1; bit >= 0; bit --)
        {
            for (int i = 0; i <= n; i ++)
                fp[i][0] = fp[i][1] = n + 1;
            fp[0][0] = fp[0][1] = 0;
            for (int i = 1; i <= n; i ++)
            {
                ll sum = 0;
                for (int k = i; k > 0; k --)
                {
                    sum = sum + a[k];
                    bool done = false;
                    for (ll fbit = maxbit - 1; fbit > bit; fbit --)
                    {
                        if ((sum & ((ll)(1) << fbit)) > 0 && f[fbit] == 0)
                        {
                            done = true;
                            break;
                        }
                    }
                    if (done)
                        continue;

                    fp[i][1] = min(fp[i][1], fp[k - 1][1] + 1);


                    if ((sum & ((ll)(1) << bit)) > 0)
                        continue;
                    fp[i][0] = min(fp[i][0], fp[k - 1][0] + 1);
                }


            }

                ll st = 1;
                if (fp[n][0] <= B)
                    st = 0;
                f[bit] = st;
                ///cout << bit << " " << st << " " << fp[n][0] << endl;


        }
        ll ans = 0;
        for (ll bit = 0; bit < maxbit; bit ++)
            if (f[bit])
                ans = ans + ((ll)(1) << bit);

        cout << ans << endl;
        return;
    }
    for (ll i = A; i <= B; i ++)
        aw[i] = 1;
    /// fix bit
    for (ll bit = maxbit - 1; bit >= 0; bit --)
    {
        dp[0][0][0] = dp[0][0][1] = 1;
        for (ll i = 1; i <= n; i ++)
            for (ll j = 1; j <= B; j ++)
                dp[i][j][0] = dp[i][j][1] = 0;

        for (ll i = 1; i <= n; i ++)
        {
            ll sum = 0;
            for (ll k = i; k > 0; k --)
            {
                sum += a[k];
                bool done = false;
                for (ll fbit = maxbit - 1; fbit > bit; fbit --)
                {
                    if ((sum & ((ll)(1) << fbit)) > 0 && f[fbit] == 0)
                    {
                        done = true;
                        break;
                    }
                }
                if (done)
                    continue;

                for (ll j = 1; j <= B; j ++)
                {
                    if (dp[k - 1][j - 1][1] == 1)
                        dp[i][j][1] = 1;
                }

                if ((sum & ((ll)(1) << bit)) > 0)
                    continue;

                for (ll j = 1; j <= B; j ++)
                {
                    if (dp[k - 1][j - 1][0] == 1)
                        dp[i][j][0] = 1;
                }

            }

        }
        ll st = 1;
        for (ll j = A; j <= B; j ++)
        {
            if (aw[j] && dp[n][j][0] == 1)
                st = 0;
        }

        if (st == 1)
        {
            f[bit] = 1;
            for (ll j = A; j <= B; j ++)
                aw[j] = min(aw[j], dp[n][j][1]);
        }
        else
        {
            for (ll j = A; j <= B; j ++)
                aw[j] = min(aw[j], dp[n][j][0]);
        }
        //exit(0);
    }

    ll ans = 0;
    for (ll bit = 0; bit < maxbit; bit ++)
        if (f[bit])
            ans = ans + ((ll)(1) << bit);

    cout << ans << endl;
}

int main()
{
    solve();
    return 0;
}
/**
6 1 2
8 1 2 1 5 4
*/

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