← 返回题目列表

AtCoder · past202104_i

I. 过去钓鱼

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

分数: 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).