AT_abc290_h [ABC290Ex] Bow Meow Optimization

题目描述

有 $N$ 只编号为 $1$ 到 $N$ 的狗，以及 $M$ 只编号为 $1$ 到 $M$ 的猫。现在要将这 $N+M$ 只动物以任意顺序排成一排。根据排列的方式，每只狗和猫会产生如下的“不满度”：

• 对于第 $i$ 只狗，设在它左边的猫有 $x$ 只，右边的猫有 $y$ 只，则它的不满度为 $A_i\times|x-y|$。
• 对于第 $i$ 只猫，设在它左边的狗有 $x$ 只，右边的狗有 $y$ 只，则它的不满度为 $B_i\times|x-y|$。

请你求出所有动物不满度总和的最小值。

输入格式

输入按以下格式从标准输入中给出。

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_M$

输出格式

请输出一个整数，表示最小的不满度总和。

输入输出样例 #1

输入 #1

2 2
1 3
2 4

输出 #1

6

输入输出样例 #2

输入 #2

1 2
100
100 290

输出 #2

390

输入输出样例 #3

输入 #3

5 7
522 575 426 445 772
81 447 629 497 202 775 325

输出 #3

13354

说明/提示

限制条件

• $1\leq N, M \leq 300$
• $1\leq A_i, B_i \leq 10^9$
• 输入均为整数

样例解释 1

如果从左到右依次排列为狗 $1$、猫 $2$、狗 $2$、猫 $1$，则：

• 狗 $1$ 的不满度为 $1\times|0-2|=2$
• 狗 $2$ 的不满度为 $3\times|1-1|=0$
• 猫 $1$ 的不满度为 $2\times|2-0|=4$
• 猫 $2$ 的不满度为 $4\times|1-1|=0$

因此不满度总和为 $6$。无论如何排列，不满度总和都不会小于 $6$，所以答案为 $6$。

由 ChatGPT 4.1 翻译