제출 #1165530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165530		thinknoexit	Bali Sculptures (APIO15_sculpture)	C++20	100 / 100	60 ms	328 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int dp[2020];
int dp2[101][101];
ll qs[2020];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, a, b;
    cin >> n >> a >> b;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        qs[i] = qs[i - 1] + x;
    }
    if (a == 1) {
        ll ans = (1ll << 41) - 1;
        for (ll j = 40;j >= 0;j--) {
            memset(dp, 0x3f, sizeof dp);
            dp[0] = 0;
            ans ^= (1ll << j);
            for (int i = 1;i <= n;i++) {
                for (int j = 0;j < i;j++) {
                    if (((qs[i] - qs[j]) | ans) == ans) {
                        dp[i] = min(dp[i], dp[j] + 1);
                    }
                }
            }
            if (dp[n] > b) ans ^= (1ll << j);
        }
        cout << ans << '\n';
        return 0;
    }
    ll ans = (1ll << 41) - 1;
    for (ll j = 40;j >= 0;j--) {
        memset(dp2, 0, sizeof dp2);
        dp2[0][0] = 1;
        ans ^= (1ll << j);
        for (int k = 1;k <= b;k++) {
            for (int i = k;i <= n;i++) {
                for (int j = k - 1;j < i;j++) {
                    if (!dp2[k - 1][j]) continue;
                    if (((qs[i] - qs[j]) | ans) == ans) {
                        dp2[k][i] = 1;
                    }
                }
            }
        }
        bool ch = 0;
        for (int i = a;i <= b;i++) {
            if (dp2[i][n]) ch = 1;
        }
        if (!ch) ans ^= (1ll << j);
    }
    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