699 . 拔河練習賽

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

smgshabc123

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

25.0% (3/12)

Tags

apcsc apcsc-enumerate

Description

一場拔河比賽每隊有 N 人，現在全班有 2N 個人要進行練習賽。教練紀錄了編號 i 的人和編號 j 的人有對戰欲望 aij(1≤i,j≤2N)，而分組後的團隊對戰欲則是所有分屬兩隊的人彼此對戰欲的加總。舉例而言，如果拔河比賽只有四人，分成 1,2 和 3,4 兩隊，且 a13=4,a23=5,a14=6,a24=7，那團隊對戰欲就是 22。

教練想要安排一種方法把大家分成兩隊每隊 N 人，使得團隊對戰欲最強，請問你這個團隊對戰欲是多少。

Input Format

輸入第一行是正整數 N，代表每隊人數。
接著 2N 行是 2N 個空白分隔的整數，代表題目敘述中的 aij(1≤i,j≤2N)。

輸入保證 1≤N≤14，1≤aij≤109，且 aij=aji 和 aii=0。

Output Format

輸出一行一個整數代表在適當分配下，最強團隊對戰欲。

Sample Input 1

1
0 5
5 0

Sample Output 1

5

Sample Input 2

2
0 7 6 4
7 0 2 5
6 2 0 8
4 5 8 0

Sample Output 2

26

Hints

Problem Source

NPSC

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~16 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 6000 524288 65536 1 2
1 6000 524288 65536 1 2
2 6000 524288 65536 2
3 6000 524288 65536 2
4 6000 524288 65536 2
5 6000 524288 65536 2
6 6000 524288 65536 2
7 6000 524288 65536 2
8 6000 524288 65536 2
9 6000 524288 65536 2
10 6000 524288 65536 2
11 6000 524288 65536 2
12 6000 524288 65536 2
13 6000 524288 65536 2
14 6000 524288 65536 2
15 6000 524288 65536 2
16 6000 524288 65536 2
Submit
Back to Top