Overview

Select exactly \(K\) gems from \(N(\le 16)\) gems and arrange them in a circular ring to maximize the total of “vertex weights \(P_i\) + adjacent edge weights \(C_{i,j}\)”. This is solved using bit DP to find the “maximum weighted cycle of length \(K\) (circular ordering)”.

Analysis

Key Observations

• The beauty is the sum of:
  • The sum of brilliances of chosen gems \(\sum P_i\)
  • The sum of harmony values of the \(K\) edges between adjacent gems in the ring \(\sum C_{i,j}\)
• Since “which \(K\) gems to choose” and “how to arrange those \(K\) gems” are intertwined, naively trying:
  • Ways to choose \(K\) gems: \({N \choose K}\)
  • Ways to arrange them: \((K-1)!/2\) (excluding rotational and reflective equivalences) would exceed \({16 \choose 8}\cdot 7! \approx 6.5\times 10^7\) at most, and with edge additions on top of that, this is not practical.

Solution: Bit DP (Traveling Salesman Type)

• Using bit DP where the state is “the best value ending at a certain vertex using a certain subset”:
  • The number of transitions (ways to grow the subset) is bounded by about \(2^N\),
  • The optimization over orderings is absorbed by the DP.
• However, if we fix a starting point and run the standard TSP DP, we can only handle subsets containing that starting point. Therefore, in this approach, we fix the minimum-numbered element of the chosen subset as the starting point, ensuring every subset of size \(K\) is handled exactly once without duplication.

Specifically, for any chosen subset \(S\), there always exists a minimum element \(s=\min S\), so: - Fix \(s\) as the starting point - Only consider vertices \(\ge s\) in the DP

This ensures that each subset appears in exactly one iteration (for its corresponding \(s\)), with no overlap.

Algorithm

Below, we fix a particular \(s\) as the “minimum number in the chosen subset (= starting point)”.

State

Remap the \(m=N-s\) vertices \(s,s+1,\dots,N-1\) locally to \(0,1,\dots,m-1\) (local 0 corresponds to starting point \(s\)).

• \(dp[\text{mask}][u]\):
  • Using the local vertex set mask (which always includes bit 0),
  • Starting from vertex 0 and ending at vertex \(u\), forming a path,
  • The maximum value achieved
  • The value consists of: \(\sum P(\text{used vertices}) + \sum C(\text{adjacent edges on the path})\)

Initial value: - \(dp[1<<0][0] = P_0\) (starting point only)

Transition (extending the path by one vertex)

When the path ending at mask has endpoint \(u\), append an unused vertex \(v\) to the end:

[ dp[mask\cup{v}][v] = \max\Big(dp[mask][u] + C_{u,v} + P_v\Big) ]

(Adding vertex \(v\) contributes \(P_v\), and adding edge \((u,v)\) contributes \(C_{u,v}\))

Closing the cycle when length reaches \(K\)

For a state mask with exactly \(K\) vertices used, close the cycle by adding the edge from endpoint \(u\) back to starting point 0:

[ \text{beauty} = dp[mask][u] + C_{u,0} ]

This gives the “beauty of arranging \(K\) gems in a ring”, and we update the maximum ans.

Overall

• Try all \(s=0,1,\dots,N-1\) (only when \(N-s \ge K\))
• For each \(s\), perform the above DP and output the maximum ans as the answer.

Complexity

• Time complexity: \(O(N^2 2^N)\) (For each \(s\), roughly \(O(m^2 2^m)\); this is sufficient for \(N\le16\))
• Space complexity: \(O(N 2^N)\) (A DP array of size at most \((1<<N)\times N\))

Implementation Details

• To “fix the minimum element as the starting point”, for each iteration \(s\), we restrict the vertex set to \([s,N)\), and iterate mask using range(1, size, 2) (only values with the lowest bit set to 1) to ensure mask always includes bit 0.

• Since values can be negative, we initialize the DP with a sufficiently small value NEG=-10^18.

• We precompute popcount (subset size) and prune early for mask values exceeding \(K\).

• Bit scanning (b = x & -x) is used to efficiently enumerate “elements in the set” and “unused elements”.

  Source Code

import sys
from array import array

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    K = next(it)
    P = [next(it) for _ in range(N)]
    C = [[next(it) for _ in range(N)] for _ in range(N)]

    maxmask = 1 << N

    pc = [0] * maxmask
    for m in range(1, maxmask):
        pc[m] = pc[m >> 1] + (m & 1)

    bit_index = [-1] * maxmask
    for i in range(N):
        bit_index[1 << i] = i

    NEG = -10**18
    ans = NEG

    for s in range(N):
        m = N - s
        if m < K:
            continue

        verts = list(range(s, N))
        Psub = [P[v] for v in verts]
        Csub = [[C[vi][vj] for vj in verts] for vi in verts]

        size = 1 << m
        fullmask = size - 1
        dp = array('q', [NEG]) * (size * m)

        dp[m + 0] = Psub[0]  # mask=1, end=0

        for mask in range(1, size, 2):  # must include start (bit0)
            cnt = pc[mask]
            if cnt > K:
                continue
            base = mask * m

            sub = mask
            while sub:
                bit = sub & -sub
                u = bit_index[bit]
                sub -= bit

                val = dp[base + u]
                if val == NEG:
                    continue

                if cnt == K:
                    total = val + Csub[u][0]
                    if total > ans:
                        ans = total
                    continue

                rem = fullmask ^ mask
                while rem:
                    b = rem & -rem
                    v = bit_index[b]
                    rem -= b

                    newmask = mask | b
                    idx = newmask * m + v
                    cand = val + Csub[u][v] + Psub[v]
                    if cand > dp[idx]:
                        dp[idx] = cand

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.