「DROI」Round 2 划分

给定长度为 $n$ 的序列 $A$。 定义序列 $A$ 的某个子段 $[L,R]$ 的权值为: $$ \sum_{i=L}^{R}[\vert A_i - A_L \vert是完全平方数] \times \sum_{i=L}^{R}[\vert A_R - A_i \vert是完全平方数]$$ 现在你需要将序列 $A$ **不重不漏**地划分成若干个子段，使得对于 $\forall i \in [1,n]$，长度为 $i$ 的子段有 $c_i$ 个。 在此基础上，求一种划分方案使所有子段权值和最大，输出这个最大值即可。特殊地，若不存在任意一种划分方案，则输出 `-1`。 **对题意不清楚的，可见下方说明提示。** ## Input 首先输入一个整数 $n$，表示序列 $A$ 的长度。 然后输入一行 $n$ 个数，其中第 $i$ 个数表示 $A_i$。 最后再输入一行 $n$ 个数，其中第 $i$ 个数表示 $c_i$。 ## Output 输出一行一个整数，表示答案。 [samples] ## Background 与其编写苍白无力的背景，不如出更有质量的题。 ## Note #### 样例解释 对于样例一，一种最优划分是分别在第二、三个数后面将序列断开。 对于样例二，一种最优划分是分别在第三、四、五、八个数后面将序列断开。 ------------ #### 数据范围 **「本题采用捆绑测试」** - $\operatorname{Subtask} 1(10\%)$：$n \leq 20$。 - $\operatorname{Subtask} 2(20\%)$：$n \leq 50,\sum_{i=1}^{n}c_i \leq 20$。 - $\operatorname{Subtask} 3(20\%)$：$n \leq 50,\forall i>5,c_i=0$。 - $\operatorname{Subtask} 4(50\%)$：无特殊限制。 对于 $100\%$ 的数据：$0 \leq c_i\leq n \leq 120,1 \leq a_i \leq 10^4$。 ------------ #### 说明提示 - 我们规定，$0$ 是完全平方数。 - $[P]=1$ 当且仅当 $P$ 是真命题，否则 $[P]=0$。