← 返回题目列表

AtCoder · past201912_g

G. 司

中文机器翻译题面 查看原题

警告

在日本标准时间 2019 年 12 月 29 日凌晨 05:00 之前请勿提及此问题。如有违反,可要求赔偿。

考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。

问题陈述

您正在编写一个程序,该程序可以最佳地划分 N 贵公司员工,员工 1, \ldots, N,最多分为三组。

对于所有员工对 i, j (1 \leq i < j \leq N),人工智能已经计算出幸福感 如果这两名员工属于同一组,就会出现 A_{i,j} (不一定是正数)。

设分组的合意性为 A_{i,j} 所有对员工 i, j 属于同一组(如果不存在这样的对,则可取性为 0)。找出分组的最大可能的期望值。

约束

  • 2 \leq N \leq 10
  • -10^6 \leq A_{i,j} \leq 10^6
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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

考虑创建以下三个组:包含 Employee 的组 1, 2,3,一个包含 Employee 的组 4, 5,以及 Employee 组 6。有四对员工属于同一组: (1,2), (1,3), (2,3), (4,5),为了满足 A_{1,2} + A_{1,3} + A_{2,3} + A_{4,5} = 10 + 10 + 10 + 10 = 40。这是最优分组。


示例输入 2

3
1 1
1

示例输出 2

3

所有员工可能属于同一组。