제출 #1165530

#제출 시각아이디문제언어결과실행 시간메모리
1165530thinknoexitBali Sculptures (APIO15_sculpture)C++20
100 / 100
60 ms328 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...