A7416 | $小枫的三角形游戏$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小枫、小午和小安正在玩一个多边形上的游戏。 小枫在纸上画了一个正 $n$ 边形，顶点按顺时针依次编号为 $1, 2, \dots, n$。 在每个顶点 $i$ 上，小午写了一个正整数 $a_i$。 游戏规则如下： - 初始时，小安的得分为 $0$。 - 小安可以重复执行以下操作任意多次： 1. 选择三个之前从未选过的顶点 $i, j, k$，画出以这三个点为顶点的三角形。 2. 得分增加 $a_i \cdot a_j \cdot a_k$。 3. 但不能画出与之前任何已画三角形有正面积重叠的三角形（即两个三角形的内部不能有公共部分）。 小安希望最大化最终得分，你能帮小安算出最大可能得分吗？

每个测试点包含多个测试用例。 第一行一个整数 $t$——测试用例的数量。 每个测试用例包含两行： - 第一行一个整数 $n$——多边形的顶点数。 - 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$——每个顶点上的数值。 数据保证所有测试用例的 $n^3$ 之和不超过 $400^3$。

对于每个测试用例，输出一行一个整数，表示小安能获得的最大得分。

输入 #1

6
3
1 2 3
4
2 1 3 4
6
2 1 2 1 1 1
6
1 2 1 3 1 5
9
9 9 8 2 4 4 3 5 3
9
9 9 3 2 4 4 8 5 3

输出 #1

C++ 编辑器

输入

输出