P6203 [USACO07CHN] The Bovine Accordion and Banjo Orchestra G

FJ’s $2N$ cows ($3 \leq N \leq 1000$) are preparing to hold a concert. Among them, $N$ cows are accordion players, and the other $N$ cows are banjo players. Each accordion player has a talent index $A_i$ ($0 \leq A_i \leq 1000$), and each banjo player also has a talent index $B_i$ ($0 \leq B_i \leq 1000$). FJ needs to pair accordion players with banjo players. Pairing the $i$-th accordion player with the $j$-th banjo player produces a profit of $A_i \times B_j$. Unfortunately, FJ’s cows have a strange quirk: if the $i$-th accordion player is paired with the $j$-th banjo player, then accordion players $i+1 \sim N$ will not choose to pair with banjo players $1 \sim j-1$. This causes a lot of trouble for FJ’s pairing plan. Even worse, those disappointed cows who lose the chance to perform will, in order to ease their sadness, go to the bar in groups to drink. If accordion players numbered $x$ to $y$ are all disappointed (accordion player $x-1$ and accordion player $y+1$ do not exist or have participated in the performance), then these cows will go to the bar together, with a cost of: $$ (\sum_{k=x}^y A_k)^2 $$ Banjo players follow a similar rule. Now FJ has to carefully consider his plan. He wants you to compute his maximum profit.

The first line contains an integer $N$. The next $N$ lines each contain one integer $A_i$. The next $N$ lines each contain one integer $B_i$.

Output the maximum profit FJ can obtain.

Pair accordion player $3$ with banjo player $1$, and the profit is $25$. Accordion players $1, 2$ drink together, and the cost is $4$. Banjo players $2, 3$ drink together, and the cost is $4$. The final profit is $17$. Translated by ChatGPT 5