/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
注意
この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
あなたは、N 人の社員、社員 1, \ldots, N を 3 つ以下のグループに最適に分割するプログラムを作ろうとしている。
すでに、社員のペア i, j (1 \leqq i < j \leqq N) すべてに対して、彼らを同じグループに含めた際に生じる幸福度 A_{i,j} (正とは限らない) が AI によって計算されている。
グループ分けの好ましさを、同じグループに含まれる社員のペア i, j すべてに対する A_{i,j} の総和 (そのようなペアが存在しなければ 0) と定義する。グループ分けの好ましさの最大値を求めよ。
制約
- 2 \leqq N \leqq 10
- -1,000,000 \leqq A_{i,j} \leqq 1,000,000
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
a_{1,2} a_{1,3} \ldots a_{1, N}
a_{2,3} a_{2,4} \ldots a_{2, N}
:
a_{N-1,N}
出力
グループ分けの好ましさの最大値を出力せよ。
入力例 1
6 10 10 -10 -10 -10 10 -10 -10 -10 -10 -10 -10 10 -10 -10
出力例 1
40
社員 1,2,3 からなるグループ、社員 4,5 からなるグループ、社員 6 からなるグループの 3 つのグループを作ることを考える。このとき、同じグループに含まれる社員のペアは (1,2), (1,3), (2,3), (4,5) の 4 つ存在し、このグループ分けの好ましさは A_{1,2} + A_{1,3} + A_{2,3} + A_{4,5} = 10 + 10 + 10 + 10 = 40 となる。これが最適なグループ分けである。
入力例 2
3 1 1 1
出力例 2
3
全員を同じグループに含めても構わない。
Warning
Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.
After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
You are writing a program that optimally divides N employees in your company, Employee 1, \ldots, N, into at most three groups.
For all pairs of employees i, j (1 \leq i < j \leq N), an AI has already computed the happiness A_{i,j} (not necessarily positive) that will arise if those two employees belong to the same group.
Let the desirability of a grouping be the sum of A_{i,j} over all pairs of employees i, j that belong to the same group (if no such pair exists, the desirability is 0). Find the maximum possible desirability of a grouping.
Constraints
- 2 \leq N \leq 10
- -10^6 \leq A_{i,j} \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
a_{1,2} a_{1,3} \ldots a_{1, N}
a_{2,3} a_{2,4} \ldots a_{2, N}
:
a_{N-1,N}
Output
Print the maximum possible desirability of a grouping.
Sample Input 1
6 10 10 -10 -10 -10 10 -10 -10 -10 -10 -10 -10 10 -10 -10
Sample Output 1
40
Consider making the following three groups: a group with Employee 1, 2,3, a group with Employee 4, 5, and a group with Employee 6. There are four pairs of employees belonging to the same group: (1,2), (1,3), (2,3), (4,5), for the desirability of A_{1,2} + A_{1,3} + A_{2,3} + A_{4,5} = 10 + 10 + 10 + 10 = 40. This is the optimal grouping.
Sample Input 2
3 1 1 1
Sample Output 2
3
All employees may belong to the same group.