小 Z 的马里奥童年
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
小 Z 从计算机专业毕业了,决定去找寻自己的童年。小时候,他经常玩一款叫做马里奥的游戏,现在他准备自己开发一个非常简单的马里奥。
因为小时候玩这个游戏他操作的马里奥只有一个,他觉得不过瘾,现在他决定创造非常多的马里奥用来顶箱子。
为了简化问题,现在在一个街道上(可以看成数轴)每隔一个单位水平站着 个马里奥,编号分别为 ,每个马里奥都有一个能力值,分别为 ,即第 个马里奥有一个 的能力值。在每一个马里奥的上方有一排共 个箱子,编号也是 ,每个箱子有一个隐藏的蘑菇值,分别为 。
游戏一开始,每个马里奥都会往上跳顶掉自己头顶的那个箱子,从而获得分数,分数为马里奥的能力值与箱子隐藏蘑菇值的乘积。具体地,第 个马里奥顶掉自己头顶的第 个箱子会获得 的分数。
这样,游戏就失去了趣味性,最终获得的分数总和是固定的,就是对应位置的马里奥能力值与箱子蘑菇值的乘积之和。为了增加可玩性,现在允许玩家操作一部分编号连续的箱子或者马里奥(要么操作编号连续的箱子,要么操作编号连续的马里奥)。
- 操作的意思是将编号连续的这段区间中的箱子翻转过来,或者将编号连续的这段区间中的马里奥从左到右换一个顺序。
- 例如选取编号为 的箱子,翻转后箱子编号为 ;或者选取编号为 的马里奥,翻转后马里奥顺序为 。
现在小 Z 想知道,在只允许执行上述操作一次的情况下,他怎么操作可以使得最终获得的分数之和最高?这样,他就可以去炫耀了。
【注意】
允许翻转连续区间长度为 的箱子或马里奥,相当于一个都不翻转,这种情况也是被允许的。
输入格式
第一行一个整数 ,表示箱子和马里奥数量。
接下来一行 个整数,分别为 ,分别表示每个马里奥的能力值。
接下来一行 个整数,分别为 ,分别表示每个箱子的蘑菇值。
输出格式
输出一行一个整数,表示最大的分数之和。
输入输出样例
6
1 8 7 6 3 6
5 9 6 8 8 6
235
5
1 2 3 4 5
2 3 4 5 6
70
提示
【样例 解释说明】
翻转编号为 的箱子,也就是箱子蘑菇值为 的这三个连续箱子,得到最终分数之和为 ,并且可以证明是最优解。
【样例 解释说明】
翻转任意区间长度为 的 个箱子,相当于没有翻转,得到的最终分数之和为 ,并且可以证明是最优解。
【数据范围】
本题共 个测试点,对于全部数据 。
具体数据点分布如下:
测试点 | 特殊性质 | ||
---|---|---|---|
无 | |||
保证 按照从小到大的顺序给出, 按照从大到小的顺序给出 | |||
保证 按照从大到小的顺序给出, 按照从小到大的顺序给出 | |||
无 | |||