P16169 [ICPC 2015 NAIPC] Sand Art

在艺术展上，经常会有展位让孩子们创作自己的沙画。这种艺术通常是用一个罐子或瓶子，填充不同颜色的沙子层来制作。今年，一种新的容器被用来装饰，代替了瓶子！这个容器是一个玻璃盒！ 盒子有一个二维的矩形面，厚度恰好为 $1$ 个单位。在玻璃盒内部，放置了 $n-1$ 个垂直隔板，将其分隔成 $n$ 个部分。在下面的示例中，盒子被 3 个隔板分成了 4 个部分： :::align{center}  ::: 有时，孩子们希望每种颜色在每个部分中都有特定的量。他们为每种部分和沙子颜色的组合指定了一个最小值和最大值。你的任务是帮助他们确定如何使艺术品尽可能平衡。这通过最小化整体沙子高度最高的部分与整体沙子高度最低的部分之间的高度差来实现。

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个输入的第一行包含 4 个空格分隔的整数 $n$、$m$、$w$、$h$，其中： - $n$（$2 \leq n \leq 200$）是部分的数量 - $m$（$1 \leq m \leq 200$）是沙子颜色的数量 - $w, h$（$1 \leq w, h \leq 5000$）是盒子的宽度和高度（深度始终为 $1$） 下一行包含 $m$ 个空格分隔的实数（最多保留三位小数）$v$（$0 < v \leq w \cdot h$），表示每种颜色沙子的总体积。不一定要使用所有沙子，但必须满足每个部分的最小值要求。 再下一行包含 $n-1$ 个空格分隔的实数（最多保留三位小数）$x$（$0 < x < w$），表示每个隔板到左侧墙壁的距离。保证这些 $x$ 值按递增顺序排序。 接下来的 $n$ 行，每行包含 $m$ 个空格分隔的实数（最多保留三位小数）$min$（$0 \leq min \leq w \cdot h$）。第 $i$ 行的第 $j$ 个元素是部分 $i$ 中必须放置的沙子颜色 $j$ 的最小量。 再接下来的 $n$ 行，每行包含 $m$ 个空格分隔的实数（最多保留三位小数）$max$（$0 \leq max \leq w \cdot h$）。第 $i$ 行的第 $j$ 个元素是部分 $i$ 中允许放置的沙子颜色 $j$ 的最大量，并且满足 $min_{ij} \leq max_{ij}$。

输出一个实数，四舍五入精确到三位小数，表示各部分沙子高度的最大值与最小值之间可能的最小差值。输入保证始终存在一种满足约束条件的沙子分配方案。

翻译由 DeepSeek V3.2 完成