提出 #45152095

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int a[n+1][n+1];
    for (int i = 1; i <= n; ++i) {
        for (int j= i+1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }
    long long dp[(1 << n)]; // dp[s] = najbolje resenje za podskup s;
    fill(dp, dp+(1 << n), 0);
    dp[0] = 0;
    for (int s = 0; s < (1 << n); ++s) {
        if (__builtin_popcount(s) == 2) {
            vector<int> t;
            for (int i = 0; i < n; ++i) {
                if ((1 << i) & s) {
                    t.push_back(i);
                }
            }
            dp[s] = a[t[0]+1][t[1]+1];
        }
        for (int j = s; j > 0; j = s & (j - 1)) {
            dp[s] = max(dp[s], dp[j]+dp[j^s]);
        }
    }
    cout << dp[(1 << n)-1] << '\n';
}

提出情報

ジャッジ結果