916 . IOdine ICe

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

$Tyellow$

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

76.0% (19/25)

Tags

ioicamp ioicamp-2025

Description

韓信有一些兵，這些兵住進了帳篷裡面，帳篷排成了 $N \times M$ 的行列，每個帳篷可能有許多兵也可能沒有。現在韓信要點名了，他希望每一排的兵的總數量跟每一列的兵的總數量都相同，不然這樣子排成的陣會不平衡，班長就要去睡公園。這些兵可能一開始的排法不滿足條件，因此他們需要進行調度。每一步可以把一個兵移到相鄰的位置，但不能超出邊界，求滿足韓信的需求的最小步數。

輸入保證一定存在一個方法滿足韓信的需求，也就是說總人數是 $lcm(N, M)$ 的倍數。

Input Format

第一行是兩個整數 $N, M$。

接下來 $N$ 行，每行有 $M$ 個整數，第 $i$ 行的第 $j$ 個整數 $A_{i,j}$ 代表第 $i$ 排的第 $j$ 團有多少人。

  • $1 \leq N, M \leq 10^ 6$
  • $1 \leq N \times M \leq 10^ 6$
  • $0 \leq A_{i,j} \leq 10^ 6$
  • $\sum A_{i, j}$ 為 $lcm(N, M)$ 的倍數。

Output Format

請輸出一個整數，代表最少需要幾步。

Sample Input 1

2 2
3 4
4 5

Sample Output 1

2

Sample Input 2

2 3
1 4 4
2 5 2

Sample Output 2

3

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~29 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
Submit
Back to Top