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
Task U - Grouping
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1058 Byte
Status
Exec Time 96 ms
Memory 4864 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
× 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