Vasya And The Mushrooms
Contest: Educational Codeforces Round 48 (Rated for Div. 2)
Difficulty rating: 1800
Tags: dp, implementation

Vasya's house is situated in a forest, and there is a mushroom glade near it. The glade consists of two rows, each of which can be divided into n consecutive cells. For each cell Vasya knows how fast the mushrooms grow in this cell (more formally, how many grams of mushrooms grow in this cell each minute). Vasya spends exactly one minute to move to some adjacent cell. Vasya cannot leave the glade. Two cells are considered adjacent if they share a common side. When Vasya enters some cell, he instantly collects all the mushrooms growing there.

Vasya begins his journey in the left upper cell. Every minute Vasya must move to some adjacent cell, he cannot wait for the mushrooms to grow. He wants to visit all the cells exactly once and maximize the total weight of the collected mushrooms. Initially, all mushrooms have a weight of 0. Note that Vasya doesn't need to return to the starting cell.

Help Vasya! Calculate the maximum total weight of mushrooms he can collect.

Input format:
The first line contains the number n (1 ≤ n ≤ 3·105) — the length of the glade.

The second line contains n numbers a1, a2, ..., an (1 ≤ ai ≤ 106) — the growth rate of mushrooms in the first row of the glade.

The third line contains n numbers b1, b2, ..., bn (1 ≤ bi ≤ 106) is the growth rate of mushrooms in the second row of the glade.

Output format:
Output one number — the maximum total weight of mushrooms that Vasya can collect by choosing the optimal route. Pay attention that Vasya must visit every cell of the glade exactly once.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the optimal route is as follows:

In the second test case, the optimal route is as follows:

Example input:
3
1 2 3
6 5 4

Example output:
70

Example input:
3
1 1000 10000
10 100 100000

Example output:
543210

Editorial:
A route visiting each cell exactly once can always be denoted as follows: several (possibly zero) first columns of the glade are visited in a zigzag pattern, then Vasya goes to the right until the end of the glade, makes one step up or down and goes left until he visits all remaining cells:
There are n - 1 such routes. To calculate the weight of collected mushrooms quickly, we will precompute three arrays for the first row of the glade — sum123, sum321 and sum111. sum123 will be used to compute the weight of mushrooms collected when Vasya moves to the right until the last column of the glade, sum321 — when Vasya moves to the left from the last column, and sum111 — to handle the growth of mushrooms.
$$\text{sum123}_i = \sum_{k=i}^{n} a_i \cdot k$$
$${ \mathrm { s u m 3 2 1 } } _ { i } = \sum _ { k = i } ^ { n } a _ { i } \cdot ( n - k + 1 )$$
$$\text{sum111}_i = \sum_{k=i}^{n} a_k$$
Also we have to compute the same arrays for the second row of the glade.
Let's iterate on the number of columns Vasya will pass in a zigzag pattern and maintain the weight of mushrooms he will collect while doing so. Then we have to add the weight of the mushrooms Vasya will gather while moving to the right, and then — while moving to the left. The first can be handled by arrays sum123 and sum111, the second — by arrays sum321 and sum111.