Submission #45169062

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
// namespace r = ranges;
#define BE(x) x.begin(), x.end()
using ll = long long;
template<class T> using vec = vector<T>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector g (n, vec<ll>(n));
    for (int i = 0; i+1 < n; ++i)
    for (int j = i+1; j < n; ++j) {
        cin >> g[i][j];
    }
    auto rec = [&](auto& rec, unsigned int f=0, ll v=0ll) -> ll {
        if (n-popcount(f) < 2) return v;
        int s = countr_one(f);
        f |= 1<<s;
        ll r = 0ll;
        for (int t = s+1; t < n; ++t) {
            if (f&1<<t) continue;
            r = max(r, rec(rec, f|1<<t, v+g[s][t]));
        }
        return r;
    };
    if (n&1) {
        ll ans = 0ll;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, rec(rec, 1<<i));
        }
        cout << ans << '\n';
    } else {
        cout << rec(rec) << '\n';
    }
}

Submission Info

Judge Result