P9375 "DROI" Round 2 Partition

Instead of writing a weak background story, it is better to provide a higher-quality problem.

Given a sequence $A$ of length $n$. Define the weight of a subarray $[L, R]$ of sequence $A$ as: $$ \sum_{i=L}^{R}[\vert A_i - A_L \vert是完全平方数] \times \sum_{i=L}^{R}[\vert A_R - A_i \vert是完全平方数]$$ Now you need to partition sequence $A$ into several subarrays **without overlap and without omission**, such that for every $i \in [1, n]$, there are exactly $c_i$ subarrays of length $i$. Based on this, find a partition plan that maximizes the sum of weights of all subarrays, and output this maximum value. In particular, if no valid partition plan exists, output `-1`. **If the statement is unclear, please see the explanation in the Hint section below.**

First, input an integer $n$, representing the length of sequence $A$. Then input one line with $n$ numbers, where the $i$-th number is $A_i$. Finally input one line with $n$ numbers, where the $i$-th number is $c_i$.

Output one line containing one integer, representing the answer.

#### Sample Explanation For Sample 1, one optimal partition is to cut the sequence after the 2nd and 3rd numbers. For Sample 2, one optimal partition is to cut the sequence after the 3rd, 4th, 5th, and 8th numbers. ------------ #### Constraints **"This problem uses bundled tests."** - $\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\%)$: No special constraints. For $100\%$ of the testdata: $0 \leq c_i \leq n \leq 120, 1 \leq a_i \leq 10^4$. ------------ #### Explanation - We define that $0$ is a perfect square. - $[P]=1$ if and only if $P$ is true; otherwise $[P]=0$. Translated by ChatGPT 5