Submission #45153153

---

Source Code Expand

#include <bits/stdc++.h>

#define int int64_t

using namespace std;
const int maxn = 3e5 + 10;
const int modm = 1e9 + 7;


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int graph[n][n];
    for (int i = 0; i < n; i++) {
        graph[i][i] = -1e10;
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            cin >> graph[i][j];
            graph[j][i] = graph[i][j];
        }
    }
    vector<int> dp((1 << n), 0);
    for (int i = 1; i < (1 << n); i++) {
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                if (i & (1 << x) && i & (1 << y) && x != y) {
                    dp[i] = max(dp[i], dp[i ^ (1 << x) ^ (1 << y)] + graph[x][y]);
                }
            }
        }
    }std::cout << dp[(1 << n) - 1] << "\n";
}

Submission Info

Judge Result