← 返回题目列表

AtCoder · otemae2019_f

F. 余额和硬币

中文机器翻译题面 查看原题

配点: 100 点

输入文件较大且语言速度较慢时会出现此问题。满分获取难度较大,请小心。

問題

在天平左侧的板上。 N 硬币从顶部开始垂直堆叠。 1, 硬币 我们称之为 2 , \cdots, 硬币 我们称之为 N 。由于氧化等因素,这些硬币的质量每天都在变化。i 今日硬币 j 的质量是 M_{i,j} 。

你 D 连续几天每天玩以下游戏。

  • 将任意数量的硬币从天平左侧的盘子顶部移动到右侧的盘子。 无需移动任何1 棋子。
  • 计算平衡天平所需的重物的质量。 G 。G 是左右板上堆放的硬币总质量之差的绝对值。
  • 你花费了 支付 G 。

D 编写一个程序,找出一段时间内必须支付的总成本的最小值。

制約

  • 1 \leq N \leq 2\,000.
  • 1 \leq D \leq 2\,000.
  • 1 \leq M_{i,j} \leq 1\,000\,000\,000 (1 \leq i \leq D, 1 \leq j \leq N).

小課題

  1. (8 点) N = 2.
  2. (8 点) N = 3.
  3. (14 点) N \leq 10,D \leq 10.
  4. (24 点) N \leq 200,D \leq 200.
  5. (46 点)没有额外的限制。

入力

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

N D
M_{1,1} M_{1,2} ... M_{1,N}
M_{2,1} M_{2,2} ... M_{2,N}
\vdots
M_{D,1} M_{D,2} ... M_{D,N}

出力

在标准输出上, 计算所有带有D 一段时间内必须支付的最低总成本。 1 请按行输出。


入力例 1

3 4
10 8 3
5 7 8
9 6 1
2 8 9

出力例 1

14

如果您执行以下操作,您将支付的总费用将为 14 ,这是最小值。 另外,这个输入示例是 2, 3, 4, 5 满足约束。

  • 1 当天硬币 移动 1 页。需要支付的费用 |10 - (8+3)| = 1 。
  • 2 当天硬币 移动 1 根本不动。需要支付的费用 |5 - (7+8)| = 10 。
  • 3 当天硬币 移动 1 根本不动。需要支付的费用 |9 - (6+1)| = 2 。
  • 4 当天硬币 移动 1 页。需要支付的费用 |(2+8) - 9| = 1 。

入力例 2

10 8
50 8 226 426 123 30 114 304 230 994
402 230 316 555 193 95 547 66 171 1000
399 30 24 177 97 325 315 1 361 993
606 973 94 32 391 116 64 782 784 631
759 1000 130 503 81 538 260 41 71 118
1000 148 223 149 113 1 110 366 56 113
1000 245 104 383 171 27 244 34 204 121
55 1000 32 151 59 44 270 386 36 104

出力例 2

6733

此输入示例是一个小作业。 3, 4, 5 满足约束。


入力例 3

1 10
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

出力例 3

10000000000

此输入示例是一个小作业。 3, 4, 5 满足约束。 输出是 32 请注意,它可能不适合位整数类型。