繁华模拟赛 ljw分雕塑

/*

用f[i][k]表示考虑到第i个雕塑，分成k组，可不可行（这是一个bool类型的数组）

转移：

f[i][k]=f[j][k-1],sum[i]-sum[j]合法

*/

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const int max_n = ;

const ll inf = 1e15;

inline int getnum() {

    int ans = ; char c; bool flag = false;

    while (!isdigit(c = getchar()) && c != '-');

    if (c == '-') flag = true; else ans = c - '';

    while (isdigit(c = getchar())) ans = ans *  + c - '';

    return ans * (flag ? - : );

}

int a[max_n], limit_A, limit_B, n;;

namespace part1 {

    const int max_n_small = ;

    bool able[max_n_small][max_n_small];

    inline bool check(ll ba, ll tar) {

        memset(able, , sizeof(able));

        able[][] = true;

        for (int i = ; i <= n; i++)

            for (int j = ; j <= limit_B; j++) {

                ll sum = a[i];

                for (int k = i - ; k >= ; k--) {

                    if (able[k][j - ] && (sum | ba) < tar) {

                        able[i][j] = true;

                        break;

                    }

                    sum += a[k];

                }

            }

        for (int i = limit_A; i <= limit_B; i++)

            if (able[n][i])

                return true;

        return false;

    }

    inline void solve() {

        ll sum = ;

        for (int i = ; i <= n; i ++)

            sum += a[i];

        sum <<= ;

        int max_bit = ;

        for (; sum >> max_bit; max_bit++);

        max_bit--;

        ll ans = ;

        for (int i = max_bit; i >= ; i--) {

            ll tar = ans | (1LL << i);

            if (!check(ans, tar))

                ans += (1LL << i);

        }

        cout << ans << endl;

    }

}

namespace part2 {

    const int max_n_small = ;

    bool able[max_n_small];

    int f[max_n_small];

    inline bool check(ll ba, ll tar) {

        memset(able, , sizeof(able));

        memset(f, 0x7f, sizeof(f));

        able[] = true;

        f[] = ;

        for (int i = ; i <= n; i++) {

            ll sum = a[i];

            for (int k = i - ; k >= ; k--) {

                if (able[k] && (sum | ba) < tar) {

                    able[i] = true;

                    f[i] = min(f[i], f[k] + );

                }

                sum += a[k];

            }

        }

        if (able[n] && f[n] <= limit_B)

            return true;

        else

            return false;

    }

    inline void solve() {

        ll sum = ;

        for (int i = ; i <= n; i ++)

            sum += a[i];

        sum <<= ;

        int max_bit = ;

        for (; sum >> max_bit; max_bit++);

        max_bit--;

        ll ans = ;

        for (int i = max_bit; i >= ; i--) {

            ll tar = ans | (1LL << i);

            if (!check(ans, tar))

                ans += (1LL << i);

        }

        cout << ans << endl;

    }

}

int main() {

    freopen("sculpture.in", "r", stdin);

    freopen("sculpture.out", "w", stdout);

    n = getnum(); limit_A = getnum(); limit_B = getnum();

    for (int i = ; i <= n; i++) a[i] = getnum();

    if (n > )

        part2::solve();

    else

        part1::solve();

}