提出 722c9999-3661-4683-be40-d7bfbe5b0282

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<long long> B(N + 1, 0);
    for (int i = 0; i < N; i++) {
        B[i + 1] = B[i] ^ A[i];
    }

    auto g = [&](int l, int r) {
        return B[r + 1] ^ B[l];
    };

    const long long I = (1LL << 60);
    vector<vector<long long> > dp(N, vector<long long>(N, 0));

    for (int len = 2; len <= N; len++) {
        for (int l = 0; l + len - 1 < N; l++) {
            int r = l + len - 1;
            long long best = I;
            for (int k = l; k < r; k++) {
                long long le = g(l, k);
                long long ri = g(k + 1, r);
                long long cost = dp[l][k] + dp[k + 1][r] + max(le, ri);
                if (cost < best) {
                    best = cost;
                }
            }
            dp[l][r] = best;
        }
    }

    cout << dp[0][N - 1] << endl;
    return 0;
}

結果

問題	点数	言語	結果	実行時間	メモリ
H. Magical Number Stabilizer	150	C++ (gcc)	AC	14 ms	5260 KiB