Submission #337156

#	Time	Username	Problem	Language	Result	Execution time	Memory
337156		danielcm585	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	140 ms	4460 KiB

sculpture

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2e3;
const int LOG = 45;
const int INF = 1e9;
const ll MX = 1e18;
int n, a, b;
int y[N+2], dp[N+2];
bool dp2[N+2][N+2];

bool can(ll x) {
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = INF;
        ll sum = 0;
        for (int j = i; j >= 1; j--) {
            sum += y[j];
            if ((sum|x) == x) dp[i] = min(dp[i],dp[j-1]+1);
        }
    }
    return dp[n] <= b;
}

bool can2(ll x) {
    // dp2[i][j] -> apakah bisa di idx i, byk kelompok tepat j
    memset(dp2,0,sizeof(dp2));
    dp2[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        ll sum = 0;
        for (int k = i; k >= 1; k--) {
            sum += y[k];
            for (int j = 1; j <= b; j++) {
                if ((sum|x) == x) dp2[i][j] |= dp2[k-1][j-1];
            }
        }
    }
    for (int i = a; i <= b; i++) {
        if (dp2[n][i]) return 1;
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
        cin >> y[i];
    }
    ll ans = (1ll<<(LOG+1))-1;
    if (a == 1) {
        // 0010011111111
        for (int i = LOG; i >= 0; i--) {
            if (can(ans^(1ll<<i))) ans ^= (1ll<<i);
        }
    }
    else {
        for (int i = LOG; i >= 0; i--) {
            if (can2(ans^(1ll<<i))) ans ^= (1ll<<i);
        }
    }
    cout << ans << '\n';
    return 0;
}

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