Submission #107972

#	Time	Username	Problem	Language	Result	Execution time	Memory
107972		dfistric	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	159 ms	888 KiB

sculpture

#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) FOR(i, 0, n)
#define ll long long

using namespace std;

const int MAXN = 2010;
ll arr[MAXN], pref[MAXN];
int n, a, b;
int dp[MAXN];
ll out = 0;
int dp2[MAXN][MAXN];

ll val(ll sum) {
    return ((((1LL << 60) - 1) - out) & sum);
}

int solve(int x) {
    REP(i, n) {
        dp[i] = 1e9;
        if (val(pref[i]) < (1LL << x)) dp[i] = 1;
        REP(j, i) {
            if (val(pref[i] - pref[j]) < (1LL << x)) dp[i] = min(dp[i], dp[j] + 1);
        }
    }
    return dp[n - 1];
}

void solve2(int x) {
    REP(i, n + 1) {
        dp2[i][1] = 0;
        if (val(pref[i]) < (1LL << x)) dp2[i][1] = 1;
        FOR(j, 2, n + 1) {
            dp2[i][j] = 0;
            REP(k, i) {
                if (val(pref[i] - pref[k]) < (1LL << x)) dp2[i][j] = max(dp2[i][j], dp2[k][j - 1]);
            }
        }
    }
    return;
}

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

    cin >> n >> a >> b;
    REP(i, n) cin >> arr[i];
    REP(i, n) {
        pref[i] = arr[i];
        if (i) pref[i] += pref[i - 1];
    }

    if (a == 1) {
        FORd(i, 50, 0) {
            if (solve(i) > b) out |= (1LL << i); 
        }
        cout << out << "\n";
    } else {
        FORd(i, 50, 0) {
            solve2(i);
            int fl = 0;
            FOR(j, a, b + 1) fl = max(fl, dp2[n - 1][j]);

            if (!fl) out |= (1LL << i);
        }
        cout << out << "\n";
    }

    return 0;
}

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