/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は美術館の展示会で、N 個の絵画を一列に並べて展示する担当になりました。
各絵画には 1 から N までの番号が付けられており、絵画 i の色調値は P_i です。絵画を一列に並べたとき、隣り合う絵画の色調値の差が大きいほど、鑑賞者にインパクトを与えることができます。
展示スペースには左から順に N か所の位置があり、それぞれの位置にちょうど 1 つの絵画を配置します。また、隣り合う位置の間には仕切り壁があり、合計 N - 1 か所の仕切り壁があります。左から i 番目の位置と i + 1 番目の位置の間にある仕切り壁には重み W_i が設定されています。重みの大きい壁の前では鑑賞者が立ち止まりやすいため、そこに隣り合って配置された絵画の組のインパクトがより大きく評価されます。
高橋君は N 個の絵画をすべてちょうど 1 回ずつ使い、N か所の位置に配置します。左から i 番目の位置に配置する絵画の番号を Q_i とすると、(Q_1, Q_2, \ldots, Q_N) は (1, 2, \ldots, N) の順列になります。このとき、展示全体の評価値は
\sum_{i=1}^{N-1} |P_{Q_i} - P_{Q_{i+1}}| \times W_i
で計算されます。ここで、P_{Q_i} は左から i 番目の位置に配置された絵画 Q_i の色調値を表します。
高橋君は、評価値が最大となるように絵画の配置を決めたいと考えています。N 個の絵画の色調値 P_1, P_2, \ldots, P_N と、N - 1 か所の仕切り壁の重み W_1, W_2, \ldots, W_{N-1} が与えられたとき、すべての配置の中での評価値の最大値を求めてください。
制約
- 2 \leq N \leq 16
- 1 \leq P_i \leq 10^7 (1 \leq i \leq N)
- 1 \leq W_i \leq 10^7 (1 \leq i \leq N-1)
- 入力はすべて整数である。
入力
N
P_1 P_2 \ldots P_N
W_1 W_2 \ldots W_{N-1}
- 1 行目には、絵画の個数を表す整数 N が与えられる。
- 2 行目には、各絵画の色調値を表す N 個の整数 P_1, P_2, \ldots, P_N がスペース区切りで与えられる。P_i は絵画 i の色調値である。
- 3 行目には、各仕切り壁の重みを表す N - 1 個の整数 W_1, W_2, \ldots, W_{N-1} がスペース区切りで与えられる。W_i は左から i 番目の位置と i + 1 番目の位置の間にある仕切り壁の重みである。
出力
評価値の最大値を整数として 1 行で出力せよ。
入力例 1
3 1 5 3 2 4
出力例 1
20
入力例 2
4 10 10 20 30 1 3 2
出力例 2
110
入力例 3
8 8 1 14 7 20 3 11 17 5 2 9 1 4 8 3
出力例 3
422
入力例 4
16 42 7 81 19 63 5 97 28 54 12 76 33 88 21 69 40 3 11 2 17 5 13 7 19 4 23 6 29 8 31 10
出力例 4
11913
入力例 5
2 1 10000000 10000000
出力例 5
99999990000000
Score : 433 pts
Problem Statement
Takahashi is in charge of displaying N paintings in a row at an art museum exhibition.
Each painting is numbered from 1 to N, and painting i has a tone value of P_i. When the paintings are arranged in a row, the greater the difference in tone values between adjacent paintings, the more impact it gives to the viewers.
The exhibition space has N positions arranged from left to right, and exactly one painting is placed at each position. Between adjacent positions, there are partition walls, totaling N - 1 partition walls. The partition wall between the i-th position from the left and the (i + 1)-th position from the left has a weight W_i. Viewers are more likely to stop in front of walls with larger weights, so the impact of the pair of paintings placed adjacent to such a wall is evaluated more highly.
Takahashi uses all N paintings exactly once and places them at the N positions. Let Q_i denote the number of the painting placed at the i-th position from the left. Then (Q_1, Q_2, \ldots, Q_N) is a permutation of (1, 2, \ldots, N). The overall evaluation score of the exhibition is calculated as
\sum_{i=1}^{N-1} |P_{Q_i} - P_{Q_{i+1}}| \times W_i
where P_{Q_i} represents the tone value of painting Q_i placed at the i-th position from the left.
Takahashi wants to determine the arrangement of paintings that maximizes the evaluation score. Given the tone values P_1, P_2, \ldots, P_N of the N paintings and the weights W_1, W_2, \ldots, W_{N-1} of the N - 1 partition walls, find the maximum evaluation score among all possible arrangements.
Constraints
- 2 \leq N \leq 16
- 1 \leq P_i \leq 10^7 (1 \leq i \leq N)
- 1 \leq W_i \leq 10^7 (1 \leq i \leq N-1)
- All input values are integers.
Input
N
P_1 P_2 \ldots P_N
W_1 W_2 \ldots W_{N-1}
- The first line contains an integer N, the number of paintings.
- The second line contains N integers P_1, P_2, \ldots, P_N separated by spaces, representing the tone values of the paintings. P_i is the tone value of painting i.
- The third line contains N - 1 integers W_1, W_2, \ldots, W_{N-1} separated by spaces, representing the weights of the partition walls. W_i is the weight of the partition wall between the i-th position from the left and the (i + 1)-th position from the left.
Output
Output the maximum evaluation score as an integer on a single line.
Sample Input 1
3 1 5 3 2 4
Sample Output 1
20
Sample Input 2
4 10 10 20 30 1 3 2
Sample Output 2
110
Sample Input 3
8 8 1 14 7 20 3 11 17 5 2 9 1 4 8 3
Sample Output 3
422
Sample Input 4
16 42 7 81 19 63 5 97 28 54 12 76 33 88 21 69 40 3 11 2 17 5 13 7 19 4 23 6 29 8 31 10
Sample Output 4
11913
Sample Input 5
2 1 10000000 10000000
Sample Output 5
99999990000000