#2483. 「CEOI2017」Building Bridges

内存限制:128 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

n 根柱子依次排列,每根柱子都有一个高度。第 i 根柱子的高度为 h_i
现在想要建造若干座桥,如果一座桥架在第 i 根柱子和第 j 根柱子之间,那么需要 (h_i-h_j)^2 的代价。
在造桥前,所有用不到的柱子都会被拆除,因为他们会干扰造桥进程。第 i 根柱子被拆除的代价为 w_i ,注意 w_i 不一定非负,因为可能政府希望拆除某些柱子。
现在政府想要知道,通过桥梁把第 1 根柱子和第 n 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

输入格式

第一行一个正整数 n
第二行 n 个空格隔开的整数,依次表示 h_1,h_2,\cdots,h_n
第三行 n 个空格隔开的整数,依次表示 w_1,w_2,\cdots,w_n

输出格式

输出一行一个整数表示最小代价,注意最小代价不一定是正数。

样例

样例输入

6
3 8 7 1 6 6
0 -1 9 1 2 0

样例输出

17

数据范围与提示

对于 100\% 的数据,有 2\le n\le 10^5;0\le h_i,\vert w_i\vert\le 10^6

  • 子任务 1( 30\% ):有 n\le 1000
  • 子任务 2( 30\% ):有 \vert w_i\vert \le 20 ,保证存在一种最优方案,除了头尾两根柱子外,最多只保留两根柱子;
  • 子任务 3( 40\% ):无特殊限制。