問題文
X先生工作的办公室里,N 行 N 按列排列了按摩椅。
从上到下第 i 行,从左 j 列的按摩椅坐标用 (i, j) 表示。
按摩椅有各种各样的性能。
(i, j) 中的按摩椅性能在 1 以上 30 以下的整数表示为 E_{i, j} ,数字越大表示越好。
另外, (i, j) 中的按摩椅的移动功率作为, 0 以上 N 以下的整数可以自由设定,设定在 P_{i, j} 。
除以
- 功率是 0 的按摩椅将不会被使用,人也不会坐。
- 功率是 0 之外的按摩椅套件总会有人坐在上面。
- (i, j) 的按摩椅 0 之外 当使用功率 P_{ i, j } 运行时, 根据功率根据動作音可以被周围的人听到, (i, j) 起 曼哈顿距离 是 P_{i, j} 以下其他按摩椅必须保持无人使用。
下图显示了一些按摩椅 这是设置 0 之外 当使用功率的示例。方格内所写的整数就分配给该位置的按摩椅。功率表示任何人不得坐在位于粉色方块的按摩椅上。
X先生设置了每把按摩椅。功率后,功率是 0 人们坐在所有不是的按摩椅上。
(i, j) 按摩椅上的人
获得E_{ i,j } \times P_{ i,j } 满意。
请尽可能增加坐在按摩椅上的人获得的满足感总和。
每个测试用例和该问题的分数计算如下:
- 在一个测试用例中,总分是坐在按摩椅上的人的总满意度。
- 所有测试用例都是 有 50 。每个测试用例的总分就是该题的得分。
入力
输入通过标准输入以以下格式给出。
第一行是一个整数
包含一个 N 。继续 N 行包含由空格分隔的整数。
包含 N 块。
\(\begin{array}{lll}
N & & \\
E_{ 0,0 } & \ldots & E_{ 0,N-1 } \\
\vdots & \ddots & \vdots \\
E_{ N-1,0 } & \ldots & E_{ N-1,N-1 }
\end{array}\)
- N 是一个整数,表示按摩椅排列的行数和列数。 满足N = 40 。 代表
- E_{ i,j } 是 (i, j) 中的按摩椅性能的整数,1 ≤ E_{i,j} ≤ 30 。 代表
出力
输出是 由 N 行,每行用空格分隔。 将 N 整数输出到标准输出。 必须满足
\(\begin{array}{lll}
P_{ 0,0 } & \ldots & P_{ 0,N-1 } \\
\vdots & \ddots & \vdots \\
P_{ N-1,0 } & \ldots & P_{ N-1,N-1 }
\end{array}\)
- P_{ i,j } 是 (i, j) 中的按摩椅的移动功率的整数,0 ≤ P_{i,j} ≤ N 。 按摩椅受
- 動作音影响 请务必设置功率请将其设置为 0 。
- 如果输出不满足上述约束, 。
关于测试用例生成
每个用例均由测试用例生成器生成。
测试用例生成器可从页面底部的链接获取。
测试用例生成器使用以下步骤生成用例。详情请参阅实现。没有必要把解释和实现都通读一遍。
- E_{ i,j } 是 x 的概率是 生成与 1/x^2 成比例。也就是说,E_{ i,j } 的值越大,出现的频率越低。
入力例1
4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16此案例仅供说明之用;输入约束( N = 40 )不满意。
出力例1
0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 42 \times 1 + 5 \times 1 + 16 \times 4 = 71 是您的分数。 请注意,您不能设置大于功率至 如果添加 N 的整数。
入力例2
40 4 2 1 1 1 1 3 1 1 1 6 1 1 2 1 1 6 17 3 5 1 2 5 2 1 1 1 1 6 12 1 4 1 3 1 1 2 1 3 2 1 1 4 1 1 4 1 1 1 12 3 1 1 1 1 7 1 1 2 1 3 1 11 1 1 1 1 1 1 1 1 1 1 2 1 1 2 4 6 3 5 6 1 1 2 1 3 4 5 1 9 1 1 2 26 6 3 1 1 1 2 4 1 2 1 1 3 1 3 1 1 2 1 1 6 1 2 1 2 1 1 1 1 16 1 1 10 1 1 1 3 7 1 1 1 1 1 2 1 1 1 1 1 19 1 1 2 3 6 1 2 12 1 2 4 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 2 1 1 1 1 9 1 1 1 8 2 2 2 1 1 2 1 1 1 1 2 1 4 1 1 1 2 1 2 1 1 1 1 1 1 1 2 5 1 1 1 3 4 3 1 30 2 1 2 19 1 2 1 1 2 1 3 1 1 1 2 4 1 15 1 4 1 1 1 1 3 4 1 1 2 1 4 1 1 1 2 1 8 8 6 1 2 2 2 2 5 2 1 1 1 1 1 1 1 3 2 1 2 1 1 16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 1 3 14 1 1 2 1 1 2 5 6 2 1 14 2 1 1 2 1 1 1 1 1 1 1 2 1 1 19 1 3 1 1 1 4 2 5 1 2 1 1 1 1 9 1 1 1 1 1 1 20 17 1 1 2 4 1 6 1 1 1 2 1 1 1 1 11 5 3 1 1 1 3 3 1 2 3 1 1 4 1 1 1 1 3 1 1 1 2 12 1 5 1 1 2 3 2 21 2 5 1 1 1 3 1 3 1 1 4 3 2 1 1 1 1 1 4 8 1 1 3 1 2 1 1 3 1 1 1 1 4 2 2 1 18 1 1 1 1 1 1 1 1 2 1 1 1 1 3 1 4 1 1 2 1 1 2 2 3 1 6 3 6 4 2 3 1 3 1 3 1 2 1 3 1 1 7 1 5 8 2 1 1 1 3 5 3 2 1 1 1 1 1 6 7 1 1 2 2 1 1 2 1 6 11 2 1 1 1 1 1 1 13 3 1 5 1 1 2 8 1 1 1 1 1 4 1 1 1 10 1 12 1 1 1 7 10 2 1 23 1 1 1 5 8 3 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 1 9 1 1 1 2 1 1 1 1 9 3 1 1 2 3 1 1 2 1 1 1 7 1 1 2 1 1 1 2 1 1 1 2 2 1 1 2 1 2 2 1 2 1 17 1 5 1 1 1 1 1 1 1 1 2 6 1 1 3 1 1 1 1 6 1 1 1 1 1 2 1 1 2 1 3 3 1 1 2 1 2 1 1 1 2 1 1 1 1 2 1 2 1 1 2 1 2 1 1 5 1 1 1 4 2 2 2 1 1 2 30 4 2 2 1 2 1 1 1 1 1 1 5 1 1 2 1 1 6 1 3 1 3 1 1 1 8 1 1 1 1 1 1 1 2 1 1 1 2 1 1 4 1 1 2 1 10 9 7 7 1 1 2 1 1 1 1 1 2 1 3 2 12 1 6 1 1 1 4 3 1 1 1 1 1 1 1 1 1 1 2 2 1 4 1 1 2 1 7 1 1 2 1 3 15 1 1 1 1 2 1 6 1 1 1 2 3 1 1 1 1 4 7 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 2 2 2 1 4 1 2 1 2 1 2 2 2 1 3 1 1 2 1 2 1 1 3 1 1 1 1 1 1 14 1 1 2 3 2 1 2 1 2 3 2 1 1 2 5 1 3 1 1 1 1 1 2 2 1 9 1 1 4 1 1 2 3 3 1 1 1 2 11 1 1 2 2 1 2 1 1 1 2 1 1 2 1 1 1 2 1 1 13 1 5 1 1 1 1 1 18 2 1 1 1 1 2 2 1 1 6 1 1 1 1 4 1 2 1 1 3 3 1 1 3 1 3 2 1 1 7 1 2 1 1 1 1 3 2 1 7 1 1 1 1 1 1 2 1 1 1 1 1 5 1 14 2 1 1 2 1 2 1 1 1 2 1 2 1 3 1 2 1 1 1 15 13 1 1 1 12 6 1 2 2 1 6 5 1 2 1 3 1 9 1 2 1 3 1 19 1 1 1 1 7 9 1 8 3 3 2 1 1 1 9 1 1 2 1 1 1 3 1 2 1 1 1 21 2 8 1 1 21 1 3 3 4 2 1 2 6 1 1 9 1 1 1 3 1 1 1 8 2 2 2 1 2 1 5 1 8 7 1 1 2 1 1 3 2 10 1 6 7 2 8 1 4 2 1 1 1 1 1 2 1 3 2 1 4 1 1 3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 7 4 8 1 5 17 2 1 2 1 1 1 1 1 1 1 2 2 1 3 1 1 2 2 9 1 1 1 1 3 1 1 2 1 1 7 28 1 5 1 1 1 2 1 2 3 1 2 1 1 1 1 1 2 1 1 1 3 1 3 1 1 1 1 3 1 19 4 1 1 1 2 1 5 1 1 1 1 1 1 2 2 1 3 1 1 1 5 2 2 1 3 1 1 3 1 1 1 1 1 1 1 2 1 1 1 4 1 1 1 4 3 4 1 2 1 3 1 10 1 1 6 2 1 1 1 1 1 1 1 6 2 1 4 2 8 1 5 2 1 1 1 1 1 1 4 1 4 1 1 1 7 1 1 3 30 1 3 1 1 3 1 1 3 2 1 1 1 6 1 1 1 1 1 1 1 2 11 1 1 1 1 1 2 1 1 3 28 5 1 1 1 1 1 1 1 3 11 1 4 1 2 1 1 4 1 6 2 1 1 1 1 1 26 1 1 7 1 2 2 2 2 1 10 1 1 1 2 1 1 2 1 2 1 1 1 1 1 1 1 2 2 3 1 1 1 1 1 1 3 1 4 2 2 1 1 11 4 1 4 5 1 1 1 2 6 17 2 1 4 22 1 9 1 11 25 3 2 1 1 1 2 7 1 2 2 1 2 16 1 2 1 1 3 1 5 3 1 1 1 1 1 1 3 6 1 3 1 4 6 1 3 4 4 1 1 1 2 1 1 1 1 5 1 6 7 1 1 1 1 1 1 1 3 1 2 1 1 1 1 4 3 1 1 1 1 9 1 1 1 1 1 3 1 4 3 1 1 1 4 1 2 1 2 7 1 4 1 1 1 1 3 1 1 1 8 1 1 1 1 1 1 1 2 1 7 2 1 4 1 1 1 3 1 1 1 2 1 6 1 1 1 2 23 4 1 1 1 1 1 1 10 1 1 1 1 1 15 14 1 1 2 1 1 1 2 1 1 5 1 12 17 1 1 1 1 1 1 3 1 1 1 1 1 1 1 7 1 2 1 1 5 4 1 1 1 7 1 3 1 1 2 1 1 1 2 3 2 2 1 1 8 2 1 2 2 2 1 1 2 1 1 1 1 6 1 5 1 1 1 1 1 1 1 3 1 1 1 7 1 2该保护套包含在测试仪中。 与
input_0.txt 相同。性能越高,出现频率越低。省略输出示例。
关于分配
我们通过以下链接提供测试用例生成器、测试器、示例输入数据和可视化器。
展示台说明
我们准备了一个可视化工具,可以可视化分数计算以及输入和输出文件的结果。
- 该可视化工具是桌面版本 谷歌浏览器 和 Mozilla 火狐浏览器 已在最新版本的 上确认操作。我们不保证它适用于所有浏览器环境。
- 此可视化工具上计算的分数不是本次比赛的分数。评分将通过在 AtCoder 上提交答案来完成。此外,在可视化工具上计算的分数并不能保证您在本次比赛中的分数。
- 请注意,我们不能保证因使用此可视化仪而造成的任何损坏。
可视化工具也包含在发行版中,发行版中的 README.html 中描述了如何使用它。