分数: 6 点
警告
2021 年 4 月 24 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
在PAST岛上,有一个钓鱼池,分为 H 水平行和 W 地图上垂直的方块列。广场上的鱼的美味 (i, j) is A_{i,j}.
最初,您位于 Square (1, 1)。现在,您将按如下方式钓鱼:
- 让 (p, q) 是您当前所在的方块。
- 您捕获了零条或一条鱼 (p, q).
- 然后,您按如下方式移动:
- if (p, q) = (H, W),你结束钓鱼;
- 否则,移至 Square (p+1, q) 或方形 (p, q+1)。然而,
- if p = H,你无法移动到广场 (p+1, q);
- if q = W,你无法移动到广场 (p, q+1).
对于每个整数 k 来自 1 通过 H+W-1,解决以下问题:
- 找出当你最多可以捕获的鱼时,你所捕获的鱼的最大可能的总美味 k 总共有鱼。
约束
- 输入中的所有值都是整数。
- 1 \le H,W \le 100
- 1 \le A_{i,j} \le 10^9
输入
输入由标准输入按以下格式给出:
H W
A_{1,1} A_{1,2} \cdots A_{1,W}
A_{2,1} A_{2,2} \cdots A_{2,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}
输出
打印 H+W-1 行。的 i- 第行应包含以下问题的答案 k=i.
示例输入 1
5 6 4 5 1 2 6 9 1 3 3 2 7 4 8 3 7 6 2 1 7 8 3 3 7 5 8 4 5 5 5 6
示例输出 1
9 16 23 30 36 41 45 48 52 53
对于 k=4,最佳捕鱼地点是,例如, (3,1),(4,1),(4,2),(4,5).
要在这些方块中捕鱼,您可以移动,例如, (1,1) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (4,1) \rightarrow (4,2) \rightarrow (4,3) \rightarrow (4,4) \rightarrow (4,5) \rightarrow (5,5) \rightarrow (5,6).