Problem5208--走迷宫(maze)

5208: 走迷宫(maze)

Time Limit: 1.000 Sec  Memory Limit: 256 MB
Submit: 5  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

小P住在森林里，他每次进城都要走一个迷宫。这个迷宫一共有两行，每一行分别都有n个格子。有一天
小P决定探索一下这个迷宫，他打算从迷宫的左上角出发，每次走一格。每个格子上有一个值，小P希望
他能够走遍每个格子，并且每个格子只走一遍。他会把途经的格子的数值和他走到该格子的步数记录下
来，然后相乘加起来得到一个结果。现在他想要这个结果的最大值。

Input

第一行输入一个数n ,表示每一行有n 个格子。
第二行输入 n个数， ai表示第一行第 i个格子的值。
第三行输入 n个数， bi表示第二行第 i个格子的值。

Output

输出一个整数，表示最大的结果。注意每个格子只访问一次，并且所有格子都需要被访问一次。

Sample Input

3
1 2 3
6 5 4

Sample Output

70

HINT

从左上角出发，一直往右走，然后走完第一行，往下走一格，接着往左走，直到走完。
结果就是0*1+1*2+2*3+3*4+4*5+5*6=70
【数据范围】
1 <=n <= 300000
1 <= ai,bi <= 10^6

Source/Category

 

[Submit] [Status]