Submission #735162

#	Time	Username	Problem	Language	Result	Execution time	Memory
735162		colossal_pepe	Bali Sculptures (APIO15_sculpture)	C++17	50 / 100	575 ms	16212 KiB

sculpture

#include <iostream>
#include <cstring>
using namespace std;

using ll = long long;

const int INF = 1e9;
const int N = 2000;

int n, a, b, dp[N + 5][N + 5];
ll x[N + 5];

bool isSubmask(ll sup, ll sub) {
    return (sup | sub) == sup;
}

int brutus(int l, int r, ll c) {
    if (r == n) return (isSubmask(c, x[r] - x[l - 1]) ? 0 : INF);
    if (dp[l][r] != -1) return dp[l][r];
    int &ret = dp[l][r];
    ret = brutus(l, r + 1, c);
    if (isSubmask(c, x[r] - x[l - 1])) ret = min(ret, 1 + brutus(r + 1, r + 1, c));
    // cout << l << ' ' << r << ' ' << ret << endl;
    return ret;
}

bool ok(ll target) {
    memset(dp, -1, sizeof dp);
    return 1 + brutus(1, 1, target) <= b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> a >> b;
    x[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        x[i] += x[i - 1];
    }
    ll c = (1ll << 42) - 1;
    for (ll bit = 41; bit >= 0; bit--) {
        c -= (1ll << bit);
        if (not ok(c)) c += (1ll << bit);
    }
    cout << c << '\n';
    return 0;
}

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