E - 宝石のネックレス 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 433 点

問題文

高橋君は宝石店で、N 個の宝石の中からちょうど K 個を選んでネックレスを作ることにしました。宝石には 1 から N までの番号が付けられており、それぞれ1個ずつあります。同じ宝石を複数回選ぶことはできません。

各宝石 i (1 \leq i \leq N) には「輝き」と呼ばれる整数値 P_i が定められています。また、宝石 i と宝石 j を隣り合わせに配置したときの「調和度」を表す整数値 C_{i,j} が定められています。調和度は対称であり、C_{i,j} = C_{j,i} を満たします。

ネックレスは環状であるため、選んだ K 個の宝石を円形に並べます。並べ方は自由に決めることができます。ネックレスの「美しさ」は、次の2つの値の合計として計算されます。

  • 選んだ K 個の宝石それぞれの輝きの合計
  • ネックレス上で隣り合うすべての宝石ペアの調和度の合計（環状に並べた K 個の宝石には、隣り合うペアがちょうど K 組あります）

例えば K = 3 で宝石 a, b, c をこの順に環状に並べた場合、美しさは P_a + P_b + P_c + C_{a,b} + C_{b,c} + C_{c,a} です。

高橋君は、ネックレスの美しさをできるだけ大きくしたいと考えています。N 個の宝石からちょうど K 個を選び、最適な環状順序で並べたときの、美しさの最大値を求めてください。

なお、C_{i,j} = C_{j,i} であるため、環状の並べ方において回転や反転で一致するものは美しさが等しくなります。したがって、最大値を求める上でこれらを区別する必要はありません。

制約

  • 3 \leq K \leq N \leq 16
  • -10^6 \leq P_i \leq 10^6 (1 \leq i \leq N)
  • -10^6 \leq C_{i,j} \leq 10^6 (1 \leq i, j \leq N)
  • C_{i,j} = C_{j,i} (1 \leq i, j \leq N)
  • C_{i,i} = 0 (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N K
P_1 P_2 \ldots P_N
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
:
C_{N,1} C_{N,2} \ldots C_{N,N}
  • 1 行目には、宝石の個数を表す整数 N と、選ぶ宝石の個数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各宝石の輝き P_1, P_2, \ldots, P_N がスペース区切りで与えられる。
  • 3 行目から N + 2 行目までの N 行で、調和度を表す N \times N の行列が与えられる。
  • 2 + i 行目 (1 \leq i \leq N) には、 C_{i,1}, C_{i,2}, \ldots, C_{i,N} がスペース区切りで与えられる。

出力

ネックレスの美しさの最大値を 1 行で出力せよ。

入力例 1

4 3
10 20 30 40
0 5 3 1
5 0 8 2
3 8 0 6
1 2 6 0

出力例 1

106

入力例 2

5 3
-10 -20 -30 -40 -50
0 -5 -3 -1 -2
-5 0 -8 -2 -4
-3 -8 0 -6 -1
-1 -2 -6 0 -3
-2 -4 -1 -3 0

出力例 2

-76

入力例 3

8 5
100 200 150 300 250 50 175 225
0 10 20 30 15 5 25 35
10 0 40 10 20 30 15 5
20 40 0 50 10 20 30 10
30 10 50 0 60 15 25 20
15 20 10 60 0 35 45 30
5 30 20 15 35 0 10 40
25 15 30 25 45 10 0 55
35 5 10 20 30 40 55 0

出力例 3

1325

入力例 4

12 8
500 -300 400 100 -200 600 350 -150 450 200 -100 300
0 50 -30 20 10 -40 60 15 -25 35 45 -10
50 0 40 -20 30 15 -35 25 50 -15 20 10
-30 40 0 55 -10 20 30 -45 15 25 -20 35
20 -20 55 0 45 -30 10 40 -15 50 30 -25
10 30 -10 45 0 25 -20 35 40 -30 15 50
-40 15 20 -30 25 0 50 -10 30 45 -35 20
60 -35 30 10 -20 50 0 40 -15 25 35 -30
15 25 -45 40 35 -10 40 0 50 -20 30 15
-25 50 15 -15 40 30 -15 50 0 45 -10 25
35 -15 25 50 -30 45 25 -20 45 0 40 -35
45 20 -20 30 15 -35 35 30 -10 40 0 50
-10 10 35 -25 50 20 -30 15 25 -35 50 0

出力例 4

3240

入力例 5

3 3
1000000 1000000 1000000
0 1000000 1000000
1000000 0 1000000
1000000 1000000 0

出力例 5

6000000

Score : 433 pts

Problem Statement

Takahashi decided to select exactly K jewels from N jewels at a jewelry store to make a necklace. The jewels are numbered from 1 to N, and there is exactly one of each. The same jewel cannot be selected more than once.

Each jewel i (1 \leq i \leq N) has an integer value called "brilliance" P_i. Additionally, there is an integer value C_{i,j} representing the "harmony" when jewel i and jewel j are placed adjacent to each other. The harmony is symmetric, satisfying C_{i,j} = C_{j,i}.

Since a necklace is circular, the selected K jewels are arranged in a ring. The arrangement can be chosen freely. The "beauty" of the necklace is calculated as the sum of the following two values:

  • The sum of the brilliance of each of the K selected jewels
  • The sum of the harmony of all adjacent pairs of jewels on the necklace (there are exactly K adjacent pairs among the K jewels arranged in a ring)

For example, if K = 3 and jewels a, b, c are arranged in this order in a ring, the beauty is P_a + P_b + P_c + C_{a,b} + C_{b,c} + C_{c,a}.

Takahashi wants to maximize the beauty of the necklace. Select exactly K jewels from the N jewels and arrange them in an optimal circular order. Find the maximum value of the beauty.

Note that since C_{i,j} = C_{j,i}, circular arrangements that coincide by rotation or reflection have the same beauty. Therefore, there is no need to distinguish between them when finding the maximum value.

Constraints

  • 3 \leq K \leq N \leq 16
  • -10^6 \leq P_i \leq 10^6 (1 \leq i \leq N)
  • -10^6 \leq C_{i,j} \leq 10^6 (1 \leq i, j \leq N)
  • C_{i,j} = C_{j,i} (1 \leq i, j \leq N)
  • C_{i,i} = 0 (1 \leq i \leq N)
  • All input values are integers.

Input

N K
P_1 P_2 \ldots P_N
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
:
C_{N,1} C_{N,2} \ldots C_{N,N}
  • The first line contains two integers separated by a space: N, the number of jewels, and K, the number of jewels to select.
  • The second line contains the brilliance values P_1, P_2, \ldots, P_N separated by spaces.
  • The following N lines (from line 3 to line N + 2) give the N \times N matrix representing the harmony values.
  • The (2 + i)-th line (1 \leq i \leq N) contains C_{i,1}, C_{i,2}, \ldots, C_{i,N} separated by spaces.

Output

Output the maximum value of the beauty of the necklace in a single line.

Sample Input 1

4 3
10 20 30 40
0 5 3 1
5 0 8 2
3 8 0 6
1 2 6 0

Sample Output 1

106

Sample Input 2

5 3
-10 -20 -30 -40 -50
0 -5 -3 -1 -2
-5 0 -8 -2 -4
-3 -8 0 -6 -1
-1 -2 -6 0 -3
-2 -4 -1 -3 0

Sample Output 2

-76

Sample Input 3

8 5
100 200 150 300 250 50 175 225
0 10 20 30 15 5 25 35
10 0 40 10 20 30 15 5
20 40 0 50 10 20 30 10
30 10 50 0 60 15 25 20
15 20 10 60 0 35 45 30
5 30 20 15 35 0 10 40
25 15 30 25 45 10 0 55
35 5 10 20 30 40 55 0

Sample Output 3

1325

Sample Input 4

12 8
500 -300 400 100 -200 600 350 -150 450 200 -100 300
0 50 -30 20 10 -40 60 15 -25 35 45 -10
50 0 40 -20 30 15 -35 25 50 -15 20 10
-30 40 0 55 -10 20 30 -45 15 25 -20 35
20 -20 55 0 45 -30 10 40 -15 50 30 -25
10 30 -10 45 0 25 -20 35 40 -30 15 50
-40 15 20 -30 25 0 50 -10 30 45 -35 20
60 -35 30 10 -20 50 0 40 -15 25 35 -30
15 25 -45 40 35 -10 40 0 50 -20 30 15
-25 50 15 -15 40 30 -15 50 0 45 -10 25
35 -15 25 50 -30 45 25 -20 45 0 40 -35
45 20 -20 30 15 -35 35 30 -10 40 0 50
-10 10 35 -25 50 20 -30 15 25 -35 50 0

Sample Output 4

3240

Sample Input 5

3 3
1000000 1000000 1000000
0 1000000 1000000
1000000 0 1000000
1000000 1000000 0

Sample Output 5

6000000