699 . 拔河練習賽

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

16.7% (1/6)

Tags

apcsc apcsc-enumerate

Description

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

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

Input Format

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

輸入保證 $1\le N\le 14$，$1\le a_{ij}\le 10^ 9$，且 $a_{ij} = a_{ji}$ 和 $a_{ii} = 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