Jump mission

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian
Chef the chief is participating in a hill jumping competition.
There are N hills arranged in a row, and each of them is assigned a unique index from 1 to N — the i^{th} hill has an index P_{i} on it. The height of the i^{th} hill is H_{i}.
Chef starts at the first hill with a goal to reach the N^{th} hill by jumping over hills from left to right (he is not allowed to jump in the other direction), jumping from i^{th} hill to j^{th} costs (H_{j}  H_{i})^{2} energy.
When chief is on the i^{th} hill, he has to prepare a special dish for the community of that hill as a thanks for letting him use their resources. This will cost him A_{i} energy (some dishes are chief's favorites and preparing it refreshes chef that why A_{i} may be negative). To make things more challenging for Chef the chief, he is allowed to jump from i^{th} hill to j^{th} if and only if i < j and P_{i} < P_{j}.
Help Chef choose the sequence of jumps that consume the minimum energy possible. (Note that it's possible at any moment that energy consumed is negative.)
Input
The first line of input contains a single integer N.
The second line contains N spaceseparated integers P_{1}, P_{2}, ... , P_{N}.
The third line contains N spaceseparated integers A_{1}, A_{2}, ... , A_{N}.
The fourth line contains N spaceseparated integers H_{1}, H_{2}, ... , H_{N}.
Output
Output a single line containing the answer to the problem i.e. the minimal possible amount of consumed energy.
Constraints
 2 ≤ N ≤ 3 × 10^{5}
 P is a permutation of the first N integer numbers
 P_{1}=1 and P_{N}=N
 10^{9} ≤ A_{i} ≤ 10^{9}
 1 ≤ H_{i} ≤ 6 × 10^{5}
Subtasks
 Subtask 1 (5 points) : 2 ≤ N ≤ 20
 Subtask 2 (15 points) : 2 ≤ N ≤ 5000
 Subtask 3 (20 points) : 2 ≤ N ≤ 3 × 10^{5}, P_{i} = H_{i} = i
 Subtask 4 (30 points) : 2 ≤ N ≤ 3 × 10^{5}, H_{i} = i
 Subtask 5 (30 points) : original constraints
Example
Input: 5 1 4 3 2 5 0 1 3 0 0 1 2 3 4 5 Output: 10
Explanation
Example case 1. jumping from first hill to 4^{th} one then to 5^{th}; the answer will be 0 + 0 + 0 + (41)^2 + (54)^2 = 10
Author:  kingofnumbers 
Editorial  http://discuss.codechef.com/problems/JUMP 
Tags  convexhull, dynamicprogramming, hard, kingofnumbers, oct15 
Date Added:  7092015 
Time Limit:  8 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions