P4655 [CEOI 2017] Building Bridges

There are $n$ pillars arranged in order, and each pillar has a height. The height of the $i$-th pillar is $h_i$. Now we want to build several bridges. If a bridge is built between the $i$-th pillar and the $j$-th pillar, it costs $(h_i-h_j)^2$. Before building bridges, all pillars that are not used will be demolished, because they would interfere with the construction process. The cost to demolish the $i$-th pillar is $w_i$. Note that $w_i$ is not necessarily non-negative, because the government may want some pillars to be demolished. Now the government wants to know the minimum total cost to connect pillar $1$ and pillar $n$ using bridges. Note that bridges cannot intersect anywhere other than at their endpoints.

The first line contains a positive integer $n$. The second line contains $n$ space-separated integers, which are $h_1,h_2,\cdots,h_n$ in order. The third line contains $n$ space-separated integers, which are $w_1,w_2,\cdots,w_n$ in order.

Output one line with one integer, the minimum total cost. Note that the minimum total cost is not necessarily positive.

For $100\%$ of the testdata, $2\le n\le 10^5;0\le h_i,\vert w_i\vert\le 10^6$. Translated by ChatGPT 5