Contest Duration: ~ (local time) (300 minutes)

Submission #11897160

Source Code Expand

Copy
```#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

ll N;
ll a[20][20];
ll sum[1000000]; // sum[S]: 集合Sに含まれる要素の和
ll dp[1000000]; // dp[S]: 集合Sの要素をグループ分けした時の得点の最大値

signed main() {
cin >> N;
rep(i, N) rep(j, N) cin >> a[i][j];
for (ull S = 0; S < (1 << N); S++)
for (int i=0; i<N; i++)
for (int j=i+1; j<N; j++)
if ((S & (1 << i)) && (S & (1 << j)))
sum[S] += a[i][j];
dp[0] = 0; // 空集合
for (ull S = 1; S < (1 << N); S++) {
dp[S] = sum[S];
for (ull U = (S-1) & S; ; U = (U-1) & S) { // Sの真部分集合
chmax(dp[S], dp[U] + sum[S - U]);
if (U == 0) break;
}
}
cout << dp[(1 << N) - 1] << endl;
return 0;
}
```

#### Submission Info

Submission Time 2020-04-13 22:37:09+0900 U - Grouping bobuhiro11 C++14 (GCC 5.4.1) 100 1058 Byte AC 96 ms 4864 KB

#### Judge Result

Set Name All
Score / Max Score 100 / 100
Status
 AC × 24
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19
Case Name Status Exec Time Memory
0_00 2 ms 2304 KB
0_01 2 ms 2304 KB
0_02 2 ms 2304 KB
0_03 94 ms 4864 KB
1_00 1 ms 256 KB
1_01 94 ms 4864 KB
1_02 94 ms 4864 KB
1_03 94 ms 4864 KB
1_04 95 ms 4864 KB
1_05 95 ms 4864 KB
1_06 94 ms 4864 KB
1_07 96 ms 4864 KB
1_08 94 ms 4864 KB
1_09 96 ms 4864 KB
1_10 95 ms 4864 KB
1_11 95 ms 4864 KB
1_12 95 ms 4864 KB
1_13 96 ms 4864 KB
1_14 94 ms 4864 KB
1_15 96 ms 4864 KB
1_16 94 ms 4864 KB
1_17 95 ms 4864 KB
1_18 96 ms 4864 KB
1_19 95 ms 4864 KB